首页 > 代码库 > Codeforces Round #283 Div.2 D Tennis Game --二分
Codeforces Round #283 Div.2 D Tennis Game --二分
题意： 两个人比赛，给出比赛序列，如果为1，说明这场1赢，为2则2赢，假如谁先赢 t 盘谁就胜这一轮，谁先赢 s 轮则赢得整个比赛。求有多少种 t 和 s 的分配方案并输出t,s。
解法： 因为要知道有哪些t,s，那么我们至少要枚举一个量，然后才能得出所有分配方案，由题意似乎枚举 t 比较方便。由于 n <= 10^5， 那么我们必须在平均logn算法级以下判断此 t 合不合法，即有没有合法的 s 。经过一些预处理，或者二分都可以达到logn的算法。
预处理sum1[i], sum2[i] 分别表示 i 的左边有多少个1和2.
容器K1,K2分别记录第 i 个1和第 i 个2出现的位置。
然后我们每次扫过去，得出每一轮谁先赢，然后判断最后两个人赢的轮数来得出答案，如果最后是X赢，那么X赢得盘数就要大于另外一个，否则此 t 不合法。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#include <map>using namespace std;#define N 100007vector<pair<int,int> > ans;vector<int> K1,K2;int sum1[N],sum2[N],a[N];int main(){ int n,i,j,t,s; while(scanf("%d",&n)!=EOF) { ans.clear(), K1.clear(), K2.clear(); for(i=1;i<=n;i++) cin>>a[i]; sum1[0] = sum2[0] = 0; int T1 = 0, T2 = 0; for(i=1;i<=n;i++) { sum1[i] = T1, sum2[i] = T2; //0~i-1 if(a[i] == 1) K1.push_back(i), T1++; else K2.push_back(i), T2++; } for(t=1;t<=n;t++) //t { int pos = 1, won1 = 0, won2 = 0, last = 0; while(pos <= n) { int c1 = sum1[pos], c2 = sum2[pos]; if(c1 + t > T1 && c2 + t > T2) break; else if(c1 + t <= T1 && c2 + t <= T2) { if(K1[c1+t-1] < K2[c2+t-1]) //1先赢 { won1++, last = 1; pos = K1[c1+t-1]; } else { won2++, last = 2; pos = K2[c2+t-1]; } } else if(c1 + t <= T1) //2已经不可能赢 { won1++, last = 1; pos = K1[c1+t-1]; } else if(c2 + t <= T2) { won2++, last = 2; pos = K2[c2+t-1]; } pos++; } if(pos == n+1) { if((last==1&&won1>won2) || (last==2&&won1<won2)) ans.push_back(make_pair(max(won1,won2),t)); } } sort(ans.begin(),ans.end()); printf("%d\n",ans.size()); for(i=0;i<ans.size();i++) printf("%d %d\n",ans[i].first,ans[i].second); } return 0;}
Codeforces Round #283 Div.2 D Tennis Game --二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。