本文主要是介绍codeforces 496d Tennis Game 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
两人进行比赛，每局赢t分即可获得本局胜利，赢满s局即获得本场比赛胜利。
现在不知道s，t。给出了两人每局的结果，让你输出s，t的方案数，以及具体方案。
思路：
枚举t，然后二分去判断是否具有合法的s。
二分判断，找到赢了第一局的人以及位置，然后从下一个位置找出赢第二局的人以及位置。一直到最后。
复杂度：O（nlogn） = n/1 + n/2 + n/3 + n/4 +……+n/n
注意：1.最后一局一定要是该比赛胜利的人赢。
2.最后的局数一定要比完并且能决出胜负。
code：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;int n;
int sum[2][MAXN], a[MAXN];
vector <pair<int, int> > res;int bs(int *sum, int p, int t)
{int ret = -1;int l = p, r = n;while(l <= r){int mid = (l+r)/2;if(sum[mid] - sum[p-1] >= t){ret = mid;r = mid-1;}elsel = mid+1;}if(ret == -1) return ret;if(ret-p+1 > 2*t-1) return -1;return ret;
}int check(int t)
{int score[2] = {0, 0};for(int p = 1;p <= n;){int idx = bs(sum[0], p, t);if(idx != -1){score[0] ++;p = idx+1;continue;}idx = bs(sum[1], p, t);if(idx != -1){score[1] ++;p = idx+1;continue;}return 0;}/*cout<<"0 :"<<score[0]<<endl;cout<<"1 :"<<score[1]<<endl;cout<<endl;*///other statusif(score[0] == score[1]) return 0;if(score[0] > score[1]){if(a[n] != 0) return 0;else return score[0];}else{if(a[n] != 1) return 0;else return score[1];}
}void solve()
{for(int i = 1;i <= n; i++){int s = check(i);if(s != 0)res.push_back(make_pair(s, i));}sort(res.begin(), res.end());cout<<res.size()<<endl;for(int i = 0;i < res.size(); i++)cout<<res[i].first<<" "<<res[i].second<<endl;
}int main()
{ios::sync_with_stdio(false);cin>>n;int tt;for(int i = 1;i <= n; i++){cin>>a[i];sum[0][i] = sum[0][i-1];sum[1][i] = sum[1][i-1];a[i]--;if(a[i]) sum[1][i]++;else sum[0][i]++;}solve();return 0;
}
这篇关于codeforces 496d Tennis Game 二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
