首页 > 代码库 > POJ 3262 【贪心】
POJ 3262 【贪心】
题意：
有n个牛在FJ的花园乱吃。
所以FJ要赶他们回牛棚。
每个牛在被赶走之前每秒吃Di个花朵。赶它回去FJ来回要花的总时间是Ti×2。在被赶走的过程中，被赶走的牛就不能乱吃
思路：
先赶走破坏力大的牛
假设序列都由二元组组成，二元组是由T和D组成，那么对一个序列有相邻的两头牛是这样的
..........(a, b) ,(c, d)....................
如果(a,b)和(c,d)交换位置了
变成新序列
..........(c,d),(a,b).......................
假设在这之前FJ已经花了x时间了。
那么赶完这两头牛的损失的量就分别为
x*b + (x + a ) * d
x*d +(x + c) * b
二者做差
得到ad - bc
若ad < bc 则有第一个序列优于第二个。
//bool cmp(cow x, cow y)
//{
// return x.t * y.d < x.d * y.t;
//}
#include <iostream>
#include <cstdio>
#include <queue>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;
struct cow
{
double t,d;
}a[2000001];
bool cmp(cow x,cow y)
{
return x.d/x.t > y.d/y.t;
}
int main()
{
int n;
scanf("%d", &n);
for(int i=0;i<n;i++)
scanf("%lf%lf",&a[i].t,&a[i].d);
sort(a,a+n,cmp);
long long sum=0,s=0;
for(int i=0;i<n;i++)
{
sum+=2*s*a[i].d;
s+=a[i].t;
}
cout<<sum<<endl;
return 0;
}
POJ 3262 【贪心】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。