本文共 1523 字，大约阅读时间需要 5 分钟。

题目大意：

有n堆牌，第 i 堆有a[i]张（正面朝上），你可以按顺序（从第一堆到最后一堆）把它们拿到手中，但是每次拿完第 i 堆以后，需要把手中b[i]张牌翻到背面。当你 手中的正面朝上的牌的数量小于b[i] 的时候，就不能取了。为了尽可能地多取，你可把前1~k堆移到后面（顺序不变），从k+1堆开始取。所以请问把前第k堆移到后面，能使取到的牌最多？

注意：数据保证b[i]之和等于a[i] 所以我觉得，一定存在k，使可以全部取完所有的牌。 我大概在结尾证明一下

思维过程：

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

具体过程：

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
   
    #include
    
     #include
     
      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娘哦~

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

转载地址：http://suuci.baihongyu.com/