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

  1. 云栖社区>
  2. 博客列表>
  3. 正文

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

kissjz 2018-02-14 10:35:54 浏览261 评论0

摘要: 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卡堆移到前面(等同于之前所有卡堆移到后面),就可以了。

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

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

 

用云栖社区APP,舒服~

【云栖快讯】青年们,一起向代码致敬,来寻找第83行吧,云栖社区邀请大神彭蕾、多隆、毕玄、福贝、点评Review你的代码,参与互动者将选取50位精彩回复赠送“向代码致敬”定制T恤1件,最终成为“多隆奖”的小伙伴还将获得由阿里巴巴提供的“多隆奖”荣誉证书和奖杯。  详情请点击

网友评论

kissjz
文章244篇 | 关注66
关注
阿里云机器学习是基于阿里云分布式计算引擎的一款机器学习算法平台。用户通过拖拉拽的方式可视化的... 查看详情
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
520表白

520表白