本文主要是介绍Codeforces Round #283 (Div. 2) D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
D. Tennis Game
题意：两个人打球，共打了n个球。先拿下t个球的赢一局，先拿下s局的获胜。给出每个球的结果，求所有可能的s和t。
思路：枚举t，二分搜索。很容易分析出来，如果A获胜，那么最后一局一定是A赢的。如果A赢下某一局，该局最后一个球一定是A赢的。做法是枚举每个t，判断是否存在一个s，使得序列合法。我们先计算出打到第i个球时，两人共赢了多少个球，然后就可以二分搜了，搜这一局会在第几个球结束，搜到最后一局如果分不出胜负，这个t就是不合法的。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;const int maxn=100010;int a[maxn];//统计打到第i个球时，两人共赢了多少个球
int sum1[maxn];
int sum2[maxn];
//已经结束的局中，两人赢了多少球
int cnt1,cnt2;struct node{int s;int t;node(int ss,int tt){s=ss; t=tt;}node(){}
}ANS[100010];bool cmp(node a,node b){if(a.s==b.s){return a.t<b.t;}return a.s<b.s;
}//二分搜索，pos表示打完后到了第几局
int bisearch(int t,int l,int r,int& pos){while(l<=r){int mid=(l+r)>>1;if(sum1[mid]-cnt1<t&&sum2[mid]-cnt2<t){l=mid+1;continue;}if(sum1[mid]-cnt1==t&&sum2[mid]-cnt2<t&&a[mid]==1){ //A获胜 pos=mid;return 1;}if(sum2[mid]-cnt2==t&&sum1[mid]-cnt1<t&&a[mid]==2){ //B获胜 pos=mid;return 2;}r=mid-1;}return 0;
}int main(){int n;cin>>n;for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]==1) sum1[i]++;else sum2[i]++;} for(int i=1;i<n;i++){sum1[i]+=sum1[i-1];sum2[i]+=sum2[i-1];}int win1;int win2;int s=0;int num=0;for(int t=1;t<=n;t++){ //枚举t cnt1=cnt2=0; //结束的局中赢的球数 win1=win2=0; //两人获胜局数 int pos=0;while(pos<n){int winner=bisearch(t,pos,n-1,pos);if(!winner)break;if(winner==1){cnt1=sum1[pos];cnt2=sum2[pos];win1++;if(pos==n-1){if(win1>win2){ANS[num]=node(win1,t);num++;}break;}}if(winner==2){cnt1=sum1[pos];cnt2=sum2[pos];win2++;if(pos==n-1){if(win1<win2){ANS[num]=node(win2,t);num++;}break;}}pos++;}}sort(ANS,ANS+num,cmp);cout<<num<<endl;for(int i=0;i<num;i++)printf("%d %d\n",ANS[i].s,ANS[i].t);return 0;
}这篇关于Codeforces Round #283 (Div. 2) D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
