http://codeforces.com/problemset/problem/1019/A
今天想起来这坑还没填。心情差.jpg
当时比赛想了一个小时dp，然后在最后10min意识到可以枚举最后所需要的人数然后贪心。。可是已经没时间来实现了，然后就果断地凉了。今天直接补了
一开始纠结，主要在于，这个决策既得考虑人数又得考虑钱，有点像背包，就很不好操作。但是实际上，n范围只有3000，所以完全可以枚举人数，在这个固定的条件下去考虑对于一特定的人数x需要多少钱，就很容易了：每次先把人数大于等于x的减到x-1，把减去的人加到党派1的支持者数量里，这个过程中挑最小的那些累计起来。在做完这些工作后就是看有没有达到人数x，如果达到了/超过了就说明行了，虽然超过的话就不是正好x但是我们只关心钱数的最小值，如果没有达到，那么还需要从剩下的所有人里从小到大累计够人数才可以。
我这里只排序1次，然后每次设置used数组表示一个人是不是在第一步里用过了。算是n^2复杂度吧。当然这个题数据貌似很水怎么都能过。。
实现的话还有一个问题就是按照我的写法遇到p为1的时候是不能设置used的，因为这个其实是针对于党派1之外的来说的。。。因为这个wa了一发。 继续阅读“[CF][贪心][枚举][思维] CF1019A”