|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include<iostream>#include<algorithm>//必须包含的头文件#include<cstdio>using namespace std;int main(){ int point[10] = {1,3,7,7,9}; int tmp = upper_bound(point, point + 5, 7) - point;//按从小到大，7最多能插入数组point的哪个位置 printf("%d
",tmp); tmp = lower_bound(point, point + 5, 7) - point; //按从小到大，7最少能插入数组point的哪个位置 printf("%d
",tmp); return 0;} |
可以当二分查找用
应用：Anton and Making Potions http://codeforces.com/contest/734/problem/C
描述：
1.处理N个potions，一个需要耗费x时间。
2.初始有n个potions，需要消耗x时间，魔法值有s。
3.有两种类型魔法：一种可以减少时间、一种可以减少处理数。
4.分别输入两大类魔法的不同型号效果和消耗魔法值。
5.两种魔法各选择0或1个型号，使得总消耗的时间最短。
思路：枚举第一种魔法，二分查找第二种不超过最大cost值的数即为最优值（贪心）。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include<iostream>#include<algorithm>#include<cstdio>#include<vector>#include<cstring>#include<map>#define ll long longusing namespace std;struct T{ ll fun,cost;}t1[200010],t2[200010];bool cmp(const T &a,const T &b){return a.cost<b.cost;}int main(){ ll n,m,k; int i,j; while(~scanf("%I64d%I64d%I64d",&n,&m,&k)) { ll x,s; scanf("%I64d%I64d",&x,&s); for(i=1;i<=m;i++) scanf("%I64d",&t1[i].fun); for(i=1;i<=m;i++) scanf("%I64d",&t1[i].cost); for(i=1;i<=k;i++) scanf("%I64d",&t2[i].fun); for(i=1;i<=k;i++) scanf("%I64d",&t2[i].cost); ll res=n*x; ll cost; t2[0].cost=-1; for(i=1;i<=m;i++) { cost=t1[i].cost; if(cost>s)continue; T a; a.cost=s-cost; int pos=upper_bound(t2,t2+k+1,a,cmp)-t2-1; if(pos==0){res=min(res,n*t1[i].fun);continue;} ll num=n-t2[pos].fun; if(num<=0){res=0;break;} else res=min(res,num*t1[i].fun); } for(i=1;i<=k;i++) { if(t2[i].cost>s)continue; ll num=n-t2[i].fun; if(num<=0){res=0;break;} else res=min(res,num*x); } printf("%I64d
",res); }} |