直接贴题面x
有$n$头奶牛跑到FJ的花园里去吃花儿了，它们分别在距离牛圈$T$分钟处吃花儿，每分钟会吃掉$D$朵卡哇伊的花儿，FJ现在要将它们给弄回牛圈，但是他每次只能弄一头回去，来回用时总共为$2*T$分钟，在这段时间内，其它的奶牛会继续吃FJ卡哇伊的花儿，速度保持不变，当然正在被赶回牛圈的奶牛就没口福了！现在要求以一种最棒的方法来尽可能的减少花儿的损失数量，求奶牛吃掉花儿的最少朵数！
话说题面好像有点问题…应该是在抓奶牛的路上这个奶牛好像就不会吃花了，也就相当于一下子到奶牛那边然后花了$2T$的时间带回去。
很显然的贪心，问题的关键在于怎么求出一个抓奶牛的顺序让被吃的花最少。
假设现在的顺序是$...ij...$这样，对于$i$前面的一段假如总时间的$T$，那么这时候被吃掉的花就是$T*d_i+(T+2t_i)*d_j$，如果交换了$i,j$，那就是$T*d_j+(T+2t_j)*d_i$，如果交换后比交换前大那不如不交换，化简一下就变成了$t_j d_i > t_i d_j$，根据这个排序统计答案就好了。
#include<cstdio> #include<algorithm> using namespace std; typedef long long lint; const int N=100005; struct cow { lint t,d; }c[N]; inline bool cmp(cow i,cow j) { return i.t*j.d<i.d*j.t; } int n;lint ans,tim; int main() { scanf("%d",&n); for(register int i=1;i<=n;i++)scanf("%lld%lld",&c[i].t,&c[i].d); sort(c+1,c+n+1,cmp); for(register int i=1;i<=n;i++)ans+=tim*c[i].d,tim+=2*c[i].t; printf("%lld",ans); }
我今天怎么好像一直都在切水题…