[补题][贪心][数据结构优化][数学] 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;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据