题目大意
有N(1<=N<=100000)头奶牛在FJ的花园里吃鲜花，对于第i头奶牛，在FJ开始把她送回家之前每分钟吃Di朵，FJ送她回家需要2*Ti分钟（来回），现在要你求最小吃掉鲜花的数量。
题解
乍一看好像没有什么思路，其实很简单的……就是按照Di/Ti从大到小排一下序，然后一个一个送回家就行，复杂度即快排复杂度O(nlog(n))。
证明如下：
假设有两头奶牛A,B，每分钟分别吃DA,DB朵鲜花，送回家分别要2*TA,2*TB分钟，最优解是FJ先送A回家接着立刻送B回家。
因为先送A回家和先送B回家不会影响其他奶牛吃鲜花的数量，只会影响A和B，因此我们只考虑A和B。那么如果先送A回家，B就吃掉DB*2*TA的鲜花，如果先送B回家，A就吃掉DA*2*TB的鲜花。因为先送A回家是最优解，所以DB*2*TA<DA*2*TB。然后解出DB/TB<DA/TA。所以Di/Ti大的先送回家，按照Di/Ti排序一下就行。
代码如下：
// WTRC - flowers
#include<cstdio>
#include<algorithm>
using namespace std;
struct cow{
int t,d;
bool operator <(const cow&x)const{return d*1.0/(1.0*t)>x.d*1.0/(1.0*x.t);}
}a[100005];
int n,Sum=0;
long long Ans=0;
int main(){
scanf("%d\n",&n);
for (int i=1;i<=n;i++){
scanf("%d%d",&a[i].t,&a[i].d);
Sum+=a[i].d;
}
sort(a+1,a+n+1);
for (int i=1;i<n;i++){
Sum-=a[i].d;
Ans+=a[i].t*2*Sum;
}
printf("%I64d",Ans);
return 0;
}
Jan 08, 2024 06:12:48 PM
JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.