hdu 4442 Physical Examination 贪心排序
Physical Examination
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6155 Accepted Submission(s): 1754
Problem Description
WANGPENG is a freshman. He is requested to have a physical examination when entering the university.
Now WANGPENG arrives at the hospital. Er….. There are so many students, and the number is increasing!
There are many examination subjects to do, and there is a queue for every subject. The queues are getting longer as time goes by. Choosing the queue to stand is always a problem. Please help WANGPENG to determine an exam sequence, so that he can finish all the physical examination subjects as early as possible.
Input
There are several test cases. Each test case starts with a positive integer n in a line, meaning the number of subjects(queues).
Then n lines follow. The i-th line has a pair of integers (ai, bi) to describe the i-th queue:
- If WANGPENG follows this queue at time 0, WANGPENG has to wait for ai seconds to finish this subject.
- As the queue is getting longer, the waiting time will increase bi seconds every second while WANGPENG is not in the queue.
The input ends with n = 0.
For all test cases, 0<n≤100000, 0≤ai,bi<231.
Output
For each test case, output one line with an integer: the earliest time (counted by seconds) that WANGPENG can finish all exam subjects. Since WANGPENG is always confused by years, just print the seconds mod 365×24×60×60.
Sample Input
5 1 2 2 3 3 4 4 5 5 6 0
Sample Output
1419
Hint
In the Sample Input, WANGPENG just follow the given order. He spends 1 second in the first queue, 5 seconds in the 2th queue, 27 seconds in the 3th queue, 169 seconds in the 4th queue, and 1217 seconds in the 5th queue. So the total time is 1419s. WANGPENG has computed all possible orders in his 120-core-parallel head, and decided that this is the optimal choice.
题意
给你n个考试,每个考试会花费ai+bi*t的花费,t表示当前的时间是多少
题解
我们首先只考虑两个,排序不同的花费分别为
a1+a2+a1b2
a2+a1+a2b1
然后我们随便推一推,可以发现这是一个贪心的策略,我们只要按照a1b2<a2b1这个来进行排序,然后跑一发就好
代码
struct node
{
LL x;
LL y;
};
bool cmp(node a,node b)
{
return a.x*b.y<b.x*a.y;
}
const LL mod=365*24*60*60;
node a[maxn];
int main()
{
int n;
while(RD(n)!=-1)
{
if(n==0)
break;
REP_1(i,n)
RD(a[i].x),RD(a[i].y);
sort(a+1,a+n+1,cmp);
LL ans=0;
REP_1(i,n)
{
ans+=a[i].x+ans*a[i].y;
ans%=mod;
}
cout<<ans%mod<<endl;
}
}
最新文章
- 数据库 &#39;xxx 的事务日志已满。若要查明无法重用日志中的空间的原因,请参阅 sys.databases 中的 log_reuse_wait_desc 列。
- How to install Shadow•socks in CentOS7
- LNMP平台搭建---Linux系统安装篇
- dede源码详细分析之--全局变量覆盖漏洞的防御
- Oracle窗口函数显示想要的行数
- 169	Majority Element [LeetCode Java实现]
- iOS开发——百度地图SDK集成
- Samba通过ad域进行认证并限制空间大小《转载》
- Eclipse下绿色安装插件Aptana、Swing
- MySQL学习笔记(4)
- Ace of Aces
- CSAPP 六个重要的实验 lab5
- 开源 java CMS - FreeCMS2.3员
- mongodb学习(六)索引
- 超简单的js评价小星星
- package.json字段全解
- MFC-注册热键
- 触摸事件,手势识别(UITouch,UIGestureRecognizer)
- Kaldi的交叉熵正则化
- BIM 开发商 --广州
热门文章
- HDU 6214 Smallest Minimum Cut 最小割,权值编码
- tf.summary.merge_all()
- git —— pycharm+git管理/编辑项目
- sql server 约束 查找
- 一步一步学习IdentityServer3 (12) 授权模式
- jar包重启脚本-restart.sh
- Zookeeper学习笔记-概念介绍
- ViewPager中的子Activity无法响应OnActivityResult的解决方法
- GMM与EM算法
- MFC+WinPcap编写一个嗅探器之六(分析模块)