本文主要是介绍codeforces 589F(二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：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;
}这篇关于codeforces 589F(二分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
