[补题][贪心][数据结构优化][数学] Gym 101775B Scapegoat

首先可以确定要分一个trouble，那一定是等分，这一点可以从公式化简得到。

所以难的问题是，给每一个trouble分几个人。当没有什么做法/头绪的时候，想一想贪心递推的操作（贪心是因为这个题数据量不应该是dp），大问题是否可以从小问题转化过来，每次多一个人的时候，这个人应该放到哪儿？可以试着遍历每一个trouble看看放在哪里会使得变小最多，但是这样是M^2的做法，但是这时候考虑“哪里小的最多”这个条件，以及，+1之后哪里变小的最多是完全取决于trouble的数值和他当前已经有的人的，所以可以用一个优先队列来存储“哪里变小的最多”这个信息！这样的话就是M^logM的算法了，可以通过本题。

自己当时为什么想挫了？主要是一开始想的把一个划分之后可以看成两个新的数，但是事实并非如此，新分出来的和原来的是不等价的，同一个trouble分出来的可以互相组合，但是不同德trouble之间不能组合，所以这种思路可以否定。所以其实每次都要考虑所有的trouble，取变小最多的那个，想到这里又觉得是M^2的算法，又没有继续，但是这时候思路已经是对的了，就可以考虑可以用什么优化，尤其是这种最值/顺序之类的问题，可以多考虑数据结构优化。

#include

using namespace std;
typedef long long LL;
const int maxn=2e5+50;
const int mod=1e9+7;

double mid;
struct node
{
    LL k,x;
    double val;
    node(LL k,LL x,double val):k(k),x(x),val(val){}
    node(){k=x=0;val=0;}
    bool operator<(const struct node& rhs)const
    {
        return val Q;

int main()
{
    int t,cs=0,n,m;
    LL tot;
    cin>>t;
    node cur;
    while(t--)
    {
        cs++;tot=0;
        while(!Q.empty())Q.pop();
        scanf("%d%d",&n,&m);
        int num=m;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            tot+=a[i];
        }
        mid=1.0*tot/m;
        for(int i=1;i<=n;i++)
            Q.push(node(1,a[i],1.0*a[i]*a[i]/2));
        m-=n;
        while(m--)
        {
            cur=Q.top();Q.pop();
            cur.k=cur.k+1;
            cur.val=1.0*cur.x*cur.x/(cur.k*(cur.k+1));
            Q.push(cur);
        }
        double ans=0.0;
        while(!Q.empty())
        {
            cur=Q.top();Q.pop();
            double tmp=1.0*cur.x/cur.k-mid;
            ans+=cur.k*tmp*tmp;
        }
        ans/=num;
        printf("Case #%d: %.10f\n",cs,ans);
    }
    return 0;
}