NOIP模拟赛 护花

时间:2022-12-16 15:40:55

【题目描述】

约翰留下他的N(N<=100000)只奶牛上山采木.他离开的时候,她们像往常一样悠闲地在草场里吃草.可是,当他回来的时候,他看到了一幕惨剧:牛们正躲在他的花园里,啃食着他心爱的美丽花朵!为了使接下来花朵的损失最小,约翰赶紧采取行动,把牛们送回牛棚. 牛们从1到N编号.第i只牛所在的位置距离牛棚Ti(1≤Ti≤2000000)分钟的路程,而在约翰开始送她回牛棚之前,她每分钟会啃食Di(1≤Di≤100)朵鲜花.无论多么努力,约翰一次只能送一只牛回棚.而运送第第i只牛事实上需要2Ti分钟,因为来回都需要时间.    写一个程序来决定约翰运送奶牛的顺序,使最终被吞食的花朵数量最小.

【输入格式】

第1行输入N,之后N行每行输入两个整数Ti和Di

【输出格式】

一个整数,表示最小数量的花朵被吞食

【样例输入】

6

3 1

2 5

2 3

3 2

4 1

1 6

【样例输出】

86

【样例解释】

 约翰用6,2,3,4,1,5的顺序来运送他的奶牛 

 

贪心,类似于国王游戏,只不过国王游戏需要高精度(还不去填坑

设S=∑(Di)

ans=min{2T[i]*(S-D[i]),2T[j]*(S-D[j])}

设2T[i]*(S-D[i])<2T[j]*(S-D[j])

可得T[i]/T[j]<(S-D[j])/(S-D[i])

显然

T[i]<T[j]且D[j]<D[i]时成立

两式相乘T[i]*D[j]<T[j]*D[i]

证毕

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 struct data
 6 {
 7     int t,d;
 8 }q[100001];
 9 long long n,sum=0,ans=0;
10 
11 bool cmp(data a,data b)
12 {
13     return a.t*b.d<b.t*a.d;
14 }
15 
16 int main()
17 {
18     cin>>n;
19     for(int i=1;i<=n;i++)
20     {
21         cin>>q[i].t>>q[i].d;
22         sum+=q[i].d;
23     }
24     sort(q+1,q+n+1,cmp);
25     for(int i=1;i<=n;i++)
26     {
27         sum-=q[i].d;
28         ans+=2*q[i].t*sum;
29     }
30     cout<<ans<<endl;
31     return 0;
32 }