欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

贪心算法推导 水题~

程序员文章站 2022-06-26 11:24:40
题目描述 在一个银行,只有一个营业员。很多人要一起办理业务,每个人需要ai分钟,不过前提是他们都立即办理。事实上,现在必定每个人都会等一段时间。由于业务的特殊性,每个人多等一分钟,他最终办事的时间就会多bi分钟。作为志愿者,你的任务就是安排他们的先后顺序,使他们最后的总时间最小。 输入:第一行一个数 ......

题目描述

在一个银行,只有一个营业员。很多人要一起办理业务,每个人需要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 }

 

通过不等式求出来的贪心是一定正确的