题目链接：http://codeforces.com/problemset/problem/589/F
题意：给出n个菜可以被品尝的时间段，求一个品尝每道菜的最大时间段t，即每道菜都可以品尝t时间并且t为所有可能情况中的最大值。
分析：典型的二分问题，将品尝时间进行二分。弄懂题意后错了一次，原因是品尝时间我是从0到所给时间的最大值进行二分的。错在了1 0 100这组样例上，应该是100按我的方法是99，这显然是错的。改成从0到maxn进行二分后就对了，不会错过边界值。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<map> #include<vector> #include<cmath> #include<set> #include<queue> using namespace std; typedef long long ll; const int maxn = 1e4 + 5; const int maxt = 1e9 + 1; const int inf = 0x3f3f3f3f; struct dish { int l,r; dish(){} dish(int l, int r):l(l),r(r){} bool operator<(const dish &di)const { if(r != di.r) return r < di.r; return l < di.l; } }d[110]; int vis[maxn]; int n; bool ok(int x) { memset(vis, 0, sizeof(vis)); int ans; for(int i = 1; i <= n; i++) { ans = 0; for(int j = d[i].l + 1; j <= d[i].r; j++) { if(!vis[j]) { vis[j] = 1; ans++; } if(ans == x) break; } if(ans < x) return false; } return true; } int main() { while(~scanf("%d",&n)) { //int ma = 0; for(int i = 1; i <= n; i++) { scanf("%d%d",&d[i].l,&d[i].r); // ma = max(ma, d[i].r); } sort(d+1, d+1+n); int l = 0, r = maxn; while(l + 1 < r) { int mid = (l + r) / 2; if(ok(mid)) l = mid; else r = mid; } //cout << "l == " << l << endl << "r == " << r << endl; if(ok(l)) printf("%d\n", n * l); else printf("0\n"); } return 0; }