[逆向思维][差分][细节][补题] Gym-101775J Straight Master

自己思考的时候问题出在哪儿呢？还是没有挖掘和抓住问题的本质特征：要分成一段一段的，肯定是从一段一段的堆起来的过程过来的，如果能把这个过程还原，就可以判断出来是不是满足要求。一段的话，就有开头和结尾，然后开始找开头和结尾就可以了。自己的具有猜想性质的算法，如果不能及时证明，则应该换思路或者让队友去写样例试图证明，或者打样例表。

想出来差分之后，还有一个细节是如何判断3这个界限，其实有更简单的判断方法但是我这里写复杂了。但是整个题目重点还是在于逆向想到差分。

2019.7.10更新：今天翻到这个题发现自己以前写的是真诡异，写了个新的清爽版本。。。

新版

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

typedef long long ll;
ll a[200015],b[200015];
int n,lst[200015];


int main()
{
    int t,cs=0;
    scanf("%d",&t);
    while(t--){
        cs++;
        printf("Case #%d: ",cs);
        scanf("%d",&n);
        ll jd=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        a[n+1]=0;
        for(int i=1;i<=n+1;i++)
            b[i]=a[i]-a[i-1],lst[i]=n+2,jd+=b[i];
        if(jd){
            puts("No");
            continue;
        }
        lst[n+2]=n+10;
        for(int i=n+1;i>=1;i--){
            if(b[i]<0) lst[i]=i;
            else lst[i]=lst[i+1];
        }
        int np=lst[1],flag=1;
        for(int i=1;i<=n&&np<=n+1&&flag;i++){
            if(b[i]>0){
                while(b[i]){
                    if(np-i<3){ flag=0; break; }
                    int cc=min(b[i],-b[np]);
                    b[i]-=cc,b[np]+=cc;
                    if(b[np]==0) np=lst[np+1];
                }
            }
        }
        if(flag) puts("Yes");
        else puts("No");
    }
    return 0;
}

旧版

 

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn=2e5+50;
const int mod=1e9+7;


LL ori[maxn],diff[maxn];
int pps,ppy,pre;
pair<int,int > ps[maxn],py[maxn];

int main()
{
    int t,n,cs=0;
    scanf("%d",&t);
    while(t--)
    {
        cs++;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&ori[i]);
        }
        ori[n+1]=0;
        pps=ppy=0;
        pre=1;
        LL sum=0;
        int flag=1;
        for(int i=n+1;i>0;i--)
        {
            diff[i]=ori[i]-ori[i-1];
            sum+=diff[i];
            if(diff[i]>0)
            {
                int tp;
                for(tp=pre;tp<=ppy;tp++)
                {
                    if(diff[i]&&py[pre].first-i<3)
                    {
                        flag=0;
                        break;
                    }
                    if(diff[i]<=py[pre].second)
                    {
                        py[pre].second-=diff[i];
                        if(!py[pre].second)
                            pre++;
                        break;
                    }
                    else
                    {
                        diff[i]-=py[pre].second;
                        pre++;
                    }
                }
                if(diff[i]>0&&tp>ppy)
                {
                    flag=0;
                    break;
                }
            }
            if(diff[i]<0)
            {
                py[++ppy]=make_pair(i,-diff[i]);

            }

        }
        if(flag&&pre<=ppy)
        {
            flag=0;
        }
        if(flag)
            cout<<"Case #"<<cs<<": Yes\n";
        else
            cout<<"Case #"<<cs<<": No\n";
    }
    return 0;
}