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\n",tmp); ????tmp?=?lower_bound(point,?point?+?5,?7)?-?point;????//按從小到大，7最少能插入數組point的哪個位置 ????printf("%d\n",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值的數即為最優(yōu)值（貪心）。

?

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?long using?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\n",res); ????} }

轉載于:https://www.cnblogs.com/bestwzh/p/6072263.html

總結

以上是生活随笔為你收集整理的(转)upper_bound()与lower_bound()使用方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。