算法学习之路|card(HDU6205)题解

本题是一道模拟题,题目大意是:

有n堆卡,每堆卡数量不等,每堆卡都有一个“惩罚值”,n堆卡惩罚值的总数等于卡片总数。你现在可以把前面任意堆卡搬到最后去,求应该搬几堆卡到最后才能保证手上的卡的数量在不小于惩罚值的情况下拿尽可能多的卡。

举个例子

卡堆卡的数量:3,4,2,6,1

惩罚值:1,4,6,2,3

那么,如果不动卡堆的顺序,拿第一堆卡:3>1,拿第二堆卡:7>5,拿第三堆卡:9<11,那么只能拿三堆卡,总数是9张,而如果把前三堆卡放到最后,那么久变成:

卡堆:6,1,3,4,2

惩罚值:2,3,1,4,6

再次拿取的话:第一堆:6>2,第二堆:7>5,第三堆:10>6,第四堆:14>12,第五堆:16=16,就可以拿所有卡片全部拿走。

ac代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define maxn 1000005
int a[maxn],b[maxn],c[maxn],d[maxn],book[maxn];
int flag=0;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        flag=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        memset(book,0,sizeof(book));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int j=1;
        for(int i=1;i<=n;i++) 
        {
            scanf("%d",&b[i]);
            c[i]=a[i]-b[i];
            if(d[j]+c[i]>=0)
                d[j]+=c[i];
            else
            {
                j++;
                book[i]=1;
            }
        }
        for(int i=n;i>0;i--)
        {
            if(book[i]==1)
            {
                flag=i;
                break;
            }
        }
        printf("%d\n",flag);
    }
}

代码看起来比加乱,思路其实很简单。

首先一个事实是,既然总惩罚值和卡数量相等,那么一定有一种移动方法可以把卡片全部拿走。

我们对上面的例子把卡片数和惩罚值相减一下:2,,0,-4,4,-2

也就是说,我们需要让这个新的数列从左到右加起来总是不小于零,换句话说,使尽可能大的书数前面。

另外考虑一点,如果有前某几个值加起来等于0,那么可以直接去掉这一部分,对结果没有影响,因为剩下那一部分和值也为0.但是和值为0的部分必须正数在前,负数在后。

换个角度,从后往前累加,如果从后往前累加某一部分和值为负,说明从前往后也是负,但如果在此基础上再往前累加一个数,和质变为正论了,说明这一部分从前往后累加也一定一直为正。那么剩下前面那一部分从前往后累加和值一定是负,把前面剩下这一部分一到后面去就离答案接近了一步。

但这样还不够,再考虑一个问题,这后面一部分和值为正的数之前依旧有可能是正值,最好把这些正值也移到前面去,那什么时候停止呢?显然当碰到一个负值的时候就应该停止,因为第一个数肯定不能为负。(这一部分和值为正的数列先叫它A吧。)

以上两个过程是多次进行的,也就是虽然题目只允许移动一次,但这一次是可以分多次移动的。

代码中是从前往后计算和值并找A,对于不是A的部分数列都标上记号,但是是从后往前检索标记,第一个检索到的有标记的卡堆以及之前的所有卡堆就是要搬到后面的卡堆。

由于A的特性,无论A中有多少堆卡,都可以看成一堆卡数量大于惩罚值的卡堆,实际上这样划分以后,整个卡堆序列会分割成几个A和非A的卡堆,且非A卡堆的卡数减惩罚值的差值的负值绝对值大小一定比它前面所有A的差值之和更大,否则在从前往后找A是,这一部分非A已经并入前面的A中了。那么在这非A之后一定还有A卡堆,才能使和值相等。那么只要最后的A卡堆移到前面(等同于之前所有卡堆移到后面),就可以了。

这样其实已经得出答案了,而且可以把所有卡堆拿光。

其实细节并没有说清楚,这个可以自己思考一下。

 

上一篇:量子计算“称霸”在望


下一篇:拨开量子计算的云雾