[BZOJ1634][Usaco2007 Jan]Protecting the Flowers 护花 贪心
1634: [Usaco2007 Jan]Protecting the Flowers 护花
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 885 Solved: 575
[Submit][Status][Discuss]
Description
Farmer John went to cut some wood and left N (2 <= N <= 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cows were in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport the cows back to their barn. Each cow i is at a location that is Ti minutes (1 <= Ti <= 2,000,000) away from the barn. Furthermore, while waiting for transport, she destroys Di (1 <= Di <= 100) flowers per minute. No matter how hard he tries,FJ can only transport one cow at a time back to the barn. Moving cow i to the barn requires 2*Ti minutes (Ti to get there and Ti to return). Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.
Input
* Line 1: A single integer
N * Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow's characteristics
第1行输入N,之后N行每行输入两个整数Ti和Di.
Output
* Line 1: A single integer that is the minimum number of destroyed flowers
一个整数,表示最小数量的花朵被吞食.
Sample Input
3 1
2 5
2 3
3 2
4 1
1 6
Sample Output
HINT
约翰用6,2,3,4,1,5的顺序来运送他的奶牛.
Source
考虑相邻的两只牛交换的条件是d[b]*t[a]<d[a]*t[b]。
按条件排序即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
LL n;
struct data{
LL t,d;
bool operator <(const data tmp)const {
return tmp.d*t<d*tmp.t;
}
}a[];
int main(){
scanf("%lld",&n);
for(int i=;i<=n;i++) scanf("%lld%lld",&a[i].t,&a[i].d);
sort(a+,a+n+);
LL sum=,tim=;
for(int i=;i<=n;i++){
sum+=a[i].d*tim;
tim+=a[i].t*;
}
printf("%lld\n",sum);
return ;
}
最新文章
- How to Install Hadoop on Ubuntu
- 记录一次centos6.4版本的VSFTP本地用户登陆的配置
- reactjs入门到实战(十)----one-first_app
- linux下LAMP环境搭建尝试
- 揪出ie和Edge的js代码
- shark错误:Query returned non-zero code: -101
- 【转】在linux内核中读写文件 -- 不错
- relative、absolute和float
- java集合系列—ArrayList
- Xamarin Android Fragment的两种加载方式
- 计蒜客NOIP模拟赛(3) D1T2 信息传递
- SDL播放YUV——循环
- SQL Server导入导出不丢主键和视图的方法
- POJ 1741 Tree (树分治入门)
- Linux-socket的close和shutdown区别及应用场景
- Python版求数组的最大连续区间
- Vector的小知识点
- 执行Socket socket = new Socket(ip, port);时抛出个异常:android.os.NetworkOnMainThreadException解决办法
- python学习——练习题(9)
- 前端开发之CSS篇二