桶排序+贪心

初识桶排序，以为是个高大上的东西，结果学完后，就这??

 步入正题，桶排是个什么东东呢?

比如3，3，4，5，6，1

桶排后:t[1]=1,t[3]=2,t[4]=1,t[5]=1,t[6]=1

好，我相信聪明的你已经看懂了，下面就是应用了。

这里有一道贪心好题https://www.luogu.com.cn/problem/P3944

---

思路:

　　我们容易发现，我们能拥有的怪物的攻击力一定是1，2，3中的一种

　　而且，选攻击力为3的要4个水晶，非常不划算

　　然后看题目要求:使用最少的疯狂药水

　　那么我们能不能先暴力求出最少的疯狂药水呢?答案是可以的

　　每次我们多用一瓶疯狂药水，就把能获得的随从全都获得,这样我们可以保证当攻击力足以踢死对面时，药水花费最少。

　　那么现在的问题简单了一些，在保持药水不变的前提下，我们能不能做一些操作让花费水晶也达到最优呢?

　　因为之前我们是选择了很多攻击力为3的随从，这是非常不划算的。如果我能用1和2攻击力的随从取代他，效果相同而花费水晶更少

　　然后我们又发现，既然这样，那攻击力为1的也很浪费呀!!能不能换成攻击力为2的呢?

　　　结论:优先级2>1>3.

　　然后因为要快速统计我们选择的1,2,3攻击力随从的个数，我们就需要桶排法。代码如下

　　

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a1,a2,a3,ans,sumn,t;
int a[30009];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)    scanf("%d",&t),a[t]++;
    for(int i=1;i+2<=30001;i+=3)
    {
        ans+=a[i],a1+=a[i];
        ans+=a[i+1]*2,a2+=a[i+1];
        ans+=a[i+2]*3,a3+=a[i+2];
        if(ans>=m)    break;

        sumn++;
    }
    while(ans>=m+3&&a3)    a3--,ans-=3;
    while(ans>=m+1&&a1)    a1--,ans-=1;
    while(ans>=m+2&&a2)    a2--,ans-=2;
    if(ans>=m)    cout<<sumn<<" "<<a1+a2+4*a3+sumn;
    else    cout<<"Human Cannot Win Dog";
    return 0;
}