0809周考

可能是贪心比较简单也比较好判断一点今天的周考更好做

A-部分背包问题

由他想拿走尽可能多的金币可以判断出一个要使用贪心。
所以我建立了三个集合，一个重量一个金额还有一个价值比，因为不能改变三个配对所以不好直接对价值比进行排序应该要创建一个序号的集合。我后面看觉得可以创建一个类，这样把三个放进去就只要创建一个集合就可以了，还要写一个排序函数cmp类似字符串排序的。

for(inti:idx){if(remain<=0){break;}if(weigh[i]<=remain){total+=value[i];remain-=weigh[i];}else{total+=unit[i]*remain;remain=0;}}

主排序就是这一段，因为我们刚刚已经根据价值比从大到小把index集合排序好了现在就要根据排序结果来安排拿什么。如果重量比剩下的上就可以把所有的价值加进结果，如果没有就要把剩下*价值比。
总体代码还是很好理解的，就是排序这块一开始不太会写没想到可以直接定义一个函数还搞了循环就导致代码多了有点错乱了。

B-混合牛奶 Mixing Milk

这道题和上一道题几乎是一样的这道题我就直接在上一题的代码上进行修改，还是三个集合组织price和weight还有一个index，因为要的是在尽可能少的钱数下买给定数量的牛奶所以根据单位价格price来进行排序，排完后判断如果给定牛奶数比最便宜的多就买下这家的所有牛奶然后再推倒下一个便宜的牛奶处，如果下一个的牛奶数比给定的多就只要买部分就可以了所以要定义一个remain来控制剩下的数量，如下：

for(inti:idx){if(remain<=0){break;}if(weigh[i]<=remain){result+=price[i]*weigh[i];remain-=weigh[i];}else{result+=price[i]*remain;remain=0;}}

和上一题没什么差别还更简单了。

C-排队接水

这题的题目一开始我理解错了，这个排序我没有想到是以这样排的所以绕弯了一会，反应过来之后还是很好做的写个cmp函数

boolcmp(constPerson&a,constPerson&b){if(a.time!=b.time){returna.time<b.time;}else{returna.num<b.num;}}

分为两个时间会不会相等。
这个我就反应过来了可以写一个Person类，存入每个人的编号和时间就不用写那么多个类排序的时候也不会怕打乱相配的时间与数字。后面就很好写了，因为排在后面的人不仅要等前一个人的还要等排在他前面所有人的所以要定义一个pre_time ，这个有pre_time+=p[i].time，这样就可以保证每个人的时间算的是正确的。而且怕溢出所以要使用longlong。

D-凌乱的yyy / 线段覆盖

这道题正好是我在周考前一天训练的区间问题，一看到有开始和结束我就想到了这个。为了不用创建多个集合所以我们创建一个类，应该时间类，包含开始和结束这样就只要一个集合。
一样的还是要加一个排序的函数然后判断前一个的时间是否比后一个的开始时间大

intcount=0;intlast=-1;for(inti=0;i<n;i++){if(g[i].start>=last){count++;last=g[i].end;}}

所以在前几题的和之前训练的基础上还是很好解的。

E-小 A 的糖果

这题不知道为什么明明我的分数是一百但是没有AC。 看完题解了应该是我定义的是int不是longlong导致溢出
这题和之前做过的排身高问题很相似，从左到右修正排序内容，为了更好排序可以人为将第一个数字设为0，然后从左到右排序如果有超出给定数字就用当前的减去这个多余的，答案加上多余的数字。

for(inti=1;i<=n;i++){if(a[i-1]+a[i]>x){LL d=a[i-1]+a[i]-x;ans+=d;a[i]-=d;}}

还是很好做的比之前排身高发糖果的好做，这两题需要从左到右再从右到左这道题不需要