4 条题解

  • 2
    @ 2024-12-13 18:12:30

    这是一道数学题目,跟着题目模拟递推即可,主要是理解弄清新学单词的数量,复习单词的数量,以及剩余没复习单词的数量之间的关系 第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
    上传者