排队接水 | FFY's Blog

题意

现在一个水龙头前面有 n 个人需要接水，他们的编号为 1 到 n 的整数。他们每个人有各自接水需要花费的时间，其中编号为 i 的人花费的时间为 Ti。另外每个人有各自的紧急程度，编号为 i 的人紧急程度为 Ei。现在我们需要给所有人排出一个序，使得总不和谐程度最低。我们定义一个人的等待时间为排在他前面的人和这个人花费的时间之和，一个人的不和谐程度为这个人的等待时间乘以这个人的紧急程度，总不和谐程度为所有人的
不和谐程度的和。
即我们需要求出一个 1 到 n 的排列 faig ，使得 $\sum_{i=1}^n( \sum^n _{j=1} T_{a_j} )$ 最小。

• 贪心
• 然后没了
• 类似国王游戏

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=2e5+10;
int n,t;
ll ans,s;
struct fy
{
    int t,v;double s;
    void w(){this->s=(double)this->t/(double)this->v;}
    bool operator<(const fy&a)
    const{return s<a.s;}
}q[maxn];
int read()
{
     int k=0,f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
     for(;c<='9'&&c>='0';c=getchar())k=(k<<3)+(k<<1)+c-'0';return  f?-k:k;
}
int main(){
     freopen("water.in","r",stdin);
     freopen("water.out","w",stdout);
     t=read();
     while(t--)
     {
         n=read();ans=0;s=0;
         for(int i=1;i<=n;i++)
         {q[i].t=read();q[i].v=read();q[i].w();}
         sort(q+1,q+1+n);
         for(int i=1;i<=n;i++)
         {
             s+=q[i].t;
             ans+=(ll)s*(ll)q[i].v;
        }
        printf("%lld\n",ans);
    }
     return 0;
}