[CF][贪心][枚举][思维] CF1019A

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了一发。

写的很丑的代码

 

#include

#define eps (1e-6)
using namespace std;
typedef long long LL;
const int maxn=3e3+5;
const int MOD=1e9+7;
const int INF=0x4f4f4f4f;
const int maxnode=1e6+5;

int cnt[3005];
bool Used[3005],used[3005];
int n,m,most=0;
struct pep
{
    int p,c,id;
    pep(){}
    pep(int p,int c,int id):p(p),c(c),id(id){}
    bool operator<(const struct pep&rhs)const{return c >cost[3005];

LL check(int x)//most last
{
    memcpy(used,Used,n+1);
    LL res=0;
    int cal=0;
    for (int i=2;i<=m;i++)
    {
        if(cnt[i]>=x)
        {
            for(int j=0;j