Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3262 Protecting the Flowers---贪心

Posted on 2009-08-24 20:32 Uriel 阅读(487) 评论(0)  编辑 收藏 引用 所属分类: POJ贪心
暑假集训组队赛的题。。当时WA了几次之后猜想是对D/T排序。。AC了。。赛后想了半天
/*Problem: 3262  User: Uriel 
   Memory: 1716K  Time: 250MS 
   Language: C++  Result: Accepted
*/
 

#include
<stdio.h>
#include
<algorithm>
#define I long long
using namespace std;
#define MAXN 100050
struct COW
{
    I t, p;
}
cow[ MAXN ];
bool icmp( COW a, COW b )
{
    
return 1.0 * a.p / a.t > 1.0 * b.p / b.t;
}

int main()
{
    
int n, i;
    I ans, sum;
    scanf(
"%d"&n);
    
for( i= 0;i < n; i ++ )
    
{
        scanf(
"%lld%lld"&cow[ i ].t, &cow[ i ].p );
    }

    sort( cow, cow 
+ n, icmp );
    sum 
= 2 * cow[ 0 ].t;
    ans 
= 0;
    
for( i = 1; i < n; i ++ )
    
{
        ans 
= ans + sum * cow[ i ].p;
        sum 
= sum + cow[ i ].t * 2;
    }

    printf(
"%lld\n", ans);
    
return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理