Posted on 2009-08-24 20:32
Uriel 閱讀(495)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ 、
貪心
暑假集訓(xùn)組隊(duì)賽的題。。當(dāng)時(shí)WA了幾次之后猜想是對(duì)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;
}