本文主要是介绍BestCoder Round #43，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
水了两道题，而且有一道还被hack了。。。
A题不说
B题
刚看到题目我愣了半天，后来才想明白如果先对所有数取模，那么任意两个数的和一定在0到2q之间，准确的说，是在0到2Q-2之间，而且它们对Q的模存在两个极大值点，于是我的第一版写的是从小到大遍历，先与最后一个相加获得第二个极大值点，再二分小于Q的最大值，交上去第一次RE，当时没有仔细检查，直接数组开大十倍又交了遍Ac。然后就被HACK，然后才发现两个数相加可能int存不下，改了之后还是WA，仔细检查代码，发现二分里面写漏了一个/2，而且二分可能进入死循环，这个地方也是第一次RE的原因。又改。原本以为我对二分已经能够掌握了，今天才发现其实还不行。这才AC
然后是题解里的思路，最大值一定是最后两个数相加 ，而第一个极大值点，只需要On遍历就行了。
自己的代码能力还是太低下了。。。。
二分代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX 100010
using namespace std;long long n,p,s[MAX];int bsearch(int index){if(s[index]+s[index+1]>=p)return -1;int front=index+1,rear=n-1,mid;while(front+1<rear){mid=(front+rear)/2;if(s[index]+s[mid]>=p)rear=mid-1;else if(s[index]+s[mid]<p)front=mid;}if(s[index]+s[rear]<p)return rear;return front;
}int main(){long long t,ans;while(scanf("%lld %lld",&n,&p)!=EOF){for(int i=0;i<n;i++){scanf("%lld",&t);s[i]=t%p;}sort(s,s+n);ans=(s[n-2]+s[n-1])%p;for(int i=0;i<n-1;i++){//cout<<(s[i]+s[n-1])%p;int ret=bsearch(i);if(ret!=-1)ans=max(ans,s[i]+s[ret]);}printf("%lld\n",ans);}return 0;
}
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX 100010
using namespace std;long long n,p,s[MAX];int main(){long long t,ans;while(scanf("%lld %lld",&n,&p)!=EOF){for(int i=0;i<n;i++){scanf("%lld",&t);s[i]=t%p;}sort(s,s+n);ans=(s[n-2]+s[n-1])%p;int rear=n-1,front=0;while(front<rear){while(s[front]+s[rear]>=p)rear--;ans=max(ans,s[front]+s[rear]);front++;}printf("%lld\n",ans);}return 0;
}
这篇关于BestCoder Round #43的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
