硬币游戏

【题目描述】

H 参加了一场神秘的游戏。游戏中有 n 堆硬币,第 i 堆价值 ai。每次小 H 可以选择编号相差 k 的硬币同时拿走。注意拿走后硬币不进行重标号。小 H 想知道最多能拿走多大价值的硬币。

【输入格式】

输入文件coin.in

第一行两个整数 n,k。

第二行 n 个整数。第 i 个整数表示 ai。

【输出格式】

输出文件coin.out

一行一个整数,表示拿走硬币的最大价值。

【样例输入】

7 3

7 5 8 6 4 3 2

【样例输出】

33

【数据范围】

对于 20%的数据,n<=20。

对于 40%的数据,n<=2000。

对于另外 20%的数据,k<=10。

 

认真理解题意可以发现,我么可以将每个硬币的编号模k,分成k组,同一组之间的硬币是会冲突的(既拿了一部分,就可能会有一部分不能拿),

不同组之间硬币是不会冲突的,这样问题就被简化了,我们再去考虑每一组,如果该组里面的硬币个数是偶数个,那么这一组的硬币都可以全部拿走

(好好理解),如果为奇数个的话,那么就会有一个无法拿走,在仔细分析,可以发现只可以将该组里第奇数个留下,(如果拿走第奇数个,那么前

面拿走的就会是奇数个,不符合题意),那么思路就明显了,具体参考代码就很容易明白了。

附上代码

 1 #include<Cstdio>
 2 #include<Iostream>
 3 using namespace std;
 4 int n,k,js[100010]; 
 5 long long sum[100010],a[100010],z;
 6 int main()
 7 {
 8     scanf("%d%d",&n,&k);
 9     for(int i=1;i<=n;++i)
10     {
11         scanf("%I64d",&a[i]);
12         z+=a[i];
13     }
14     for(int i=0;i<k;++i)
15     {
16         sum[i]=99999999999;
17     }
18     for(int i=1;i<=n;++i)
19     {
20         js[i%k]++;
21         if(a[i]<sum[i%k]&&js[i%k]%2==1)
22         {
23             sum[i%k]=a[i];
24         }
25     }
26     for(int i=0;i<k;++i)
27     {
28         if(js[i]%2==1)
29         z-=sum[i];
30     }
31     printf("%I64d",z);
32     return 0;
33 }

 

全部评论

相关推荐

大方的大熊猫准备进厂:1.教育背景:你希望从事什么专业的工作你的主修课就是什么;成绩优秀是你应该做的,没什么可描述的,成绩不优秀也许人家在大学忙着创业呢?(成绩优秀不一定是好事,只能说明多元化的大学你上成了高中,没有真正上明白大学,反而体现了你死板,不爱社交,没有别的突出能力) 2.实践经历:你想表达的意思没有说清楚。你是说你会个性化服务,还是你有实习经历。如果没有带来,经济收益,表彰,更好的发展前景,那你还不如说说提升了自己哪些技能。你说有人给你送锦旗我都能明白你优秀,但是你说你会xxxx,你说这话谁信,证据呢。 3.入伍经历:你描述的就是你的工作职责或者你应该做的,并没有体现出来你把这个事情做好了,而且入伍经历并不能证明你能干好你要应聘的工作,不如只写经历其余所有内容都不写。 4.荣誉技能:重点突出一下,但不要过多描述,这些荣誉的含金量懂得都懂。 重点:你要应聘什么工作(具体岗位,实习生不具体),你的期望薪资
点赞 评论 收藏
分享
学java时间比较短不到三个月,基本的技术栈都过了一遍就是都不太深,有个小项目。是继续找实习还是沉淀准备秋招呢?找实习的话会花很多时间在八股,放弃的话又怕秋招简历太难看。有无大佬支招
今天java了吗:1.一定要找实习,实习不一定要去,但是找实习过程中的面试经验和心态经验才是最重要的 2.八股本来就是大头,甚至比项目重要 3.这个时间段也是面试比较多的阶段,可以抓住机会锻炼。面试才会发现自己的不足,感觉自己会了和能给面试官娓娓道来是两码事
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务