欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-22 08:23:36
...

题目大意:

有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娘哦~

HDU 6205 card card card 解题思路【最长非零子序列】
每日中二:
我要努力,向着自己的目标前进!!