题目链接：http://codeforces.com/contest/734/problem/C
题意：
玩一个游戏，一开始升一级需要t秒时间，现在有a, b两种魔法，两种魔法分别有m1, m2种效果；
对应使用a1[i]魔法需要a2[i]金币，使用b1[i]魔法需要b2[i]金币；
每种魔法最多只能使用一次，问升到n（n<=1e+5）级最少需要多少时间；
注意：给出的b1, b2数组是升序排列的；
思路：对每一个a魔法找到最大的b1魔法jj, 即为使用此a魔法需要最少时间的情况；再找到所有jj中最小的即为答案；
因为b数组是排好序的，所以对于b数组的查找我们可以用二分；时间复杂度为nlog(n)；
代码：
1 #include <iostream>
2 #include <stdio.h>
3 #include <algorithm>
4 #include <math.h>
5 #define ll long long
6 #define MAXN 200009
7 using namespace std; 8
9 ll min(ll a, ll b){ 10 return a<b?a:b; 11 } 12
13 int main(void){ 14 int m1, m2; 15 ll aim, t, money, ans, a1[MAXN], a2[MAXN], b1[MAXN], b2[MAXN]; 16 scanf("%lld%d%d%lld%lld", &aim, &m1, &m2, &t, &money); 17 for(int i=0; i<m1; i++){ 18 scanf("%lld", &a1[i]); 19 } 20 for(int i=0; i<m1; i++){ 21 scanf("%lld", &a2[i]); 22 } 23 for(int i=0; i<m2; i++){ 24 scanf("%lld", &b1[i]); 25 } 26 for(int i=0; i<m2; i++){ 27 scanf("%lld", &b2[i]); 28 } 29 ans=t*aim; 30 for(int i=0; i<m1; i++){ 31 ll gg=aim, mm=money; 32 if(a2[i]<=mm&&a1[i]<t){ 33 ll tt=a1[i]; 34 mm-=a2[i]; 35 int pos=upper_bound(b2, b2+m2, mm)-b2; 36 if(pos>=m2){ 37 gg-=b1[m2-1]; 38 }else if(pos>0){ 39 gg-=b1[pos-1]; 40 } 41 ll jj=gg*tt; 42 ans=min(ans, jj); 43 } 44 { 45 ll gg1=aim; 46 int pos=upper_bound(b2, b2+m2, money)-b2; 47 if(pos>=m2){ 48 gg1-=b1[m2-1]; 49 }else if(pos>0){ 50 gg1-=b1[pos-1]; 51 } 52 ll jj=gg1*t; 53 ans=min(ans, jj); 54 } 55 } 56 printf("%lld\n", ans); 57 return 0; 58 }