贪心算法推导 水题~
2018-06-27 10:06:06来源:未知 阅读 ()
题目描述
在一个银行,只有一个营业员。很多人要一起办理业务,每个人需要ai分钟,不过前提是他们都立即办理。事实上,现在必定每个人都会等一段时间。由于业务的特殊性,每个人多等一分钟,他最终办事的时间就会多bi分钟。作为志愿者,你的任务就是安排他们的先后顺序,使他们最后的总时间最小。
输入:第一行一个数n,表示有n个人。接下来n行每行两个数ai,bi。
输出:一行一个整数,输出最小时间。答案对1000000009取模。
样例输入
2
1 1
2 2
样例输出
5
提示
若1先,那么代价为1+(2+1*2)=5
若2先,那么代价为2+(1+2*1)=5
对于10%的数据:1<=n<=10
对于100%数据:1<=n<=10000,0<=ai,bi<=10000
明显的贪心思想。
假设只有两个人:x和y。那么谁应该排在前面呢。(用x.a与x.b来表示x的ai与bi,y同理)
若x先,则时间要用:x.a+x.a*y.b+y.a
若y先,则时间要用:y.a+y.a*x.b+x.a
设第一个时间小于第二个时间:x.a+x.a*y.b+y.a<y.a+y.a*x.b+x.a
左边右边x.a,y.a移项抵消,只剩下:x.a*y.b<y.a*x.b。
则只要满足这条件,x就该排在y前面。就可以用这个条件来进行快排。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int mod=1000000009;
6 struct zhu{
7 int a,b;
8 }e[10010];
9 int cmp(zhu x,zhu y)
10 {
11 return x.a*y.b<y.a*x.b;//用此公式来快排重定义
12 }
13 int mark[10010];
14 int main()
15 {
16 int n;
17 scanf("%d",&n);
18 for(int i=1;i<=n;i++)scanf("%d%d",&e[i].a,&e[i].b);
19 sort(e+1,e+n+1,cmp);
20 long long ans=0;
21 for(int i=1;i<=n;i++)
22 {
23 ans=(ans+ans*e[i].b+e[i].a)%mod;//此时的顺序就是最优顺序,依次加答案即可
24 }
25 printf("%lld",ans);
26 }
通过不等式求出来的贪心是一定正确的
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 圆桌均分硬币 ——(推导式子) 2020-04-09
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash