4 条题解
-
2
这是一道数学题目,跟着题目模拟递推即可,主要是理解弄清新学单词的数量,复习单词的数量,以及剩余没复习单词的数量之间的关系 第k天: 今天学的的单词数为x 新学单词的数量:如果x大于等于k-1天新学的单词数+剩余没复习的单词数,那么新学的单词数=x-(k-1天新学的单词数+剩余没复习的单词数),否则等于0。 复习单词的数量:如果x小于k-1天新学的单词+剩余的单词,那么复习单词的数量应该等于x;否则就等于新学的单词+剩余的单词。 没复习单词的数量:如果今天学的的单词数x小于昨天剩余没复习的单词数+昨天新学的单词数那么今天没复习的单词数=昨天剩余没复习的单词数+昨天新学的单词数-x,否则等于0。 得到递推公式,初始化即可 初始化:(定义i为第i天) 当i==1时 newword[i]=words[i]; review[i]=0; left[i]=0; 代码如下:
#include<bits/stdc++.h> using namespace std; #define ll long long ll n,m,k; int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; vector<ll>words(n+1);//单词数数组 vector<ll>newword(n+1);//新学单词数组 vector<ll>review(n+1);//复习单词数组 vector<ll>left(n+1);//剩余单词数组 for(int i=1;i<=n;i++){ cin>>words[i]; //初始化,写外面从i==2开始也可,题目给的天数>=1 if(i==1){ newword[i]=words[i]; review[i]=0; left[i]=0; }else{ //递推公式 newword[i]=max(0ll,words[i]-left[i-1]-newword[i-1]); review[i]=min(left[i-1]+newword[i-1],words[i]); left[i]=max(0ll,left[i-1]+newword[i-1]-words[i]); } } //输出结果,完美~~ for(int i=0;i<m;i++){ cin>>k; cout<<newword[k]<<' '<<review[k]<<' '<<left[k]<<'\n'; } return 0; }
时间复杂度:O(n); 空间复杂度:O(n);
信息
- ID
- 968
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 549
- 已通过
- 84
- 上传者