codeforces 补题总结 2

codeforces 1251 E
这题又栽了，细节上忽略了，忘记了使用队列，想当然的挨个对付a[i],结果出现错误。

错误代码：

#include <iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<utility>
#define p pair<int,int>
#include <vector>
#define ll long long
using namespace std;
vector<ll>a[5005];
int main()
{
   int q;
   scanf("%d",&q);
   int n;
   int x;ll y;
   while(q--)
   {
       scanf("%d",&n);
       for(int i=1;i<=n;i++)
       {
           scanf("%d%lld",&x,&y);
           a[x].push_back(y);
       }
       ll res=0;
       for(int i=n-1;i>=0;i--)
       {
           sort(a[i].begin(),a[i].end());
           while(a[i].size()>n-i)
           {
               res=res+(*a[i].begin());
               a[i].erase(a[i].begin());
           }
       }
       printf("%lld\n",res);
   }
   return 0;
}

codeforce 1256 C
遇到需要开n个的数组，开成vector 形式大有好处。虽然这题没怎么用到。

#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,d;
    cin>>n>>m>>d;
    vector<int>c(m);
    for(int i=0;i<m;i++)
        cin>>c[i];
    vector<int>ans(n+2);
    int pos=n;
    for(int i=m-1;i>=0;i--)
    {
        for(int len=0;len<c[i];len++)
        {
            ans[pos-len]=i+1;
        }
        pos=pos-c[i];
    }
    int now=0;
    while(1)
    {
        while(now<n&&ans[now+1]>0) now++;
        if(now+d>=n+1) break;
        if(ans[now+d]==0)
        {
            int l=-1;
            for(int i=now+d;i<n+2;i++)
            {
                if(ans[i]!=0)
                {
                    l=i;
                    break;
                }
            }
            if(l==-1)
            {
                cout<<"NO"<<endl;
                return 0;
            }
            int r=-1;
            for(int i=l;i<n+2;i++)
            {
                if(ans[i]==ans[l]) r=i;
            }
            while(ans[now+d]==0)
            {
                swap(ans[l-1],ans[r]);
                l--;
                r--;
            }
        }
        now=now+d;
    }
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/weixin_45608039/article/details/107373976