5
25
2015
0

POJ 3262 Protecting the Flowers 贪心/排序

题目大意

有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; 
} 
Category: POJ | Tags: POJ | Read Count: 313

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com