HDU 6205 card card card 解题思路【最长非零子序列】

题目大意：

有n堆牌，第 i 堆有a[i]张（正面朝上），你可以按顺序（从第一堆到最后一堆）把它们拿到手中，但是每次拿完第 i 堆以后，需要把手中b[i]张牌翻到背面。当你 手中的正面朝上的牌的数量小于b[i] 的时候，就不能取了。为了尽可能地多取，你可把前1~k堆移到后面（顺序不变），从k+1堆开始取。所以请问把前第k堆移到后面，能使取到的牌最多？
注意：数据保证b[i]之和等于a[i]
所以我觉得，一定存在k，使可以全部取完所有的牌。
我大概在结尾证明一下
题目地址http://acm.hdu.edu.cn/showproblem.php?pid=6205

思维过程：

从第一堆开始取，一旦正面朝上的牌的数量不够了，就把它们全部移到后面 以此来试图续命 ，这样就把结束的时间延后了，那么再从新的序列开始继续上述操作。似乎这样是可以把所有牌取完的

具体过程：

1. 令c[i]=a[i]-b[i]（因为不需要输出取了多少牌，只需要知道k），把c[i]复制一遍粘贴到后面。
2. 然后令t=1，表示从第t堆开始取，然后就往后取，令ans为正面朝上的牌数，假设当取到第 i 堆时，ans<0，则令t=i+1，表示前 i 堆已经不行了，得移到后面，才有可能取得更多。重复上述操作，因为是一定能够取完的t会在小于等于n的时候就会结束。

有点像求最长非零子序列的过程

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

const int maxn=1e6+7;

int n,t[maxn<<1],st;

void hanser()
{
    for(int i=1;i<=n;++i){
        int x;scanf("%d",&x);
        t[i+n]=t[i]=x;
    }
    for(int i=1;i<=n;++i){
        int x;scanf("%d",&x);
        t[i+n]-=x;t[i]-=x;
    }//不想多开数组了，就这么写了
    st=1;
    int ans=0;
    for(int i=1;i<=(n<<1);i++){
        ans+=t[i];
        if(i-st+1==n) break;//已经全部取完了
        if(ans < 0){
            st=i+1;ans=0;
        }
    }
    printf("%d\n",st-1);
    return;
}

int main()
{
    while(~scanf("%d",&n))
        hanser();
    return 0;
}

证明：

注：讨论的都是进行过操作的新数组，即从新的数组第一堆算起。
可能有点不严谨。
假设在第 i 堆的时候已经不能取了，说明a[1]~a[i] 之和 小于 b[1] ~ b[i]之和。
因为a之和 等于 b之和，说明在i之后一定存在某个区间，使得在此区间内，a之和 大于 b之和，
那么只需快进把此区间之前的数移到后面，就能继续取下去了。
因为a之和是等于b之和的，所以最后取的那一些堆一定是 a<b 的，
所以经过有限次操作，一定可以到达这种情况的。
利用反证法证明，假设无法取完，那么说明对于任何子序列，总有b > a,那么就说明b之和大于a之和，与题意不符，所以不成立，所以一定可以取完。

大概就是这个意思，可能有点不严谨。

按照惯例
送给大家一个可爱的22娘~
下次是33娘哦~

每日中二:
我要努力，向着自己的目标前进！！