CSP第25次 202203-2 出行計劃 C/C++滿分答案

CSP曆年真題答案合集點我（連結）

下方是100分代碼，差分數組

#include <bits/stdc++.h>
using namespace std;

int can[200010]={0};//某時間做核酸能滿足的出行計劃數量
int ans[200010]={0};
int chaxun[100010]={0};
int main()
{
    int n,m,k,i,j;
    cin>>n>>m>>k;
    for(i=0;i<n;i++)
    {
        int clock,need;
        scanf("%d %d",&clock,&need);
        if(clock-k>0)
        {
            int l=clock-k-need+1;
            int r=clock-k+1;
            can[max(l,0)]++;
            can[r]--;
        }
    }
    ans[0] = can[0];
    for(i=1;i<=200010;i++)
        ans[i] = ans[i-1] + can[i];
    for(i=0;i<m;i++)
        scanf("%d",&chaxun[i]);
    for(i=0;i<m;i++)
        printf("%d\n",ans[chaxun[i]]);

    return 0;
}

           

下方是100分代碼，普通記錄數組

#include <bits/stdc++.h>
using namespace std;

int can[200010]={0};//某時間做核酸能滿足的出行計劃數量
int chaxun[200010]={0};
int main()
{
    int n,m,k,i,j;
    cin>>n>>m>>k;
    for(i=0;i<n;i++)
    {
        int clock,need;
        scanf("%d %d",&clock,&need);
        if(clock-k>0)
            for(j=clock-k;j>=0 && j>clock-k-need;j--)
                can[j]++;
    }
    for(i=0;i<m;i++)
        scanf("%d",&chaxun[i]);
    for(i=0;i<m;i++)
        printf("%d\n",can[chaxun[i]]);

    return 0;
}