pog loves szh IITime Limit: 4000/2000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2106Accepted Submission(s): 606
Problem Description
Pog and Szh are playing games.There is a sequence with numbers, Pog will choose a number A from the sequence. Szh will choose an another number named B from the rest in the sequence. Then the score will be mod .They hope to get the largest score.And what is the largest score?
Input
Several groups of data (no more than groups,).For each case: The following line contains two integers,。The following line contains integers 。
Output
For each case,output an integer means the largest score.
Sample Input
4 41 2 3 04 40 0 2 2
Sample Output
32
Source
BestCoder Round #43
有n个数，从这n个数中选出两个数，不能相同，，使得两个数相加取模后的值最大。
可以先进行排序，然后用线性的方法找最大。
排序之前先对所有的数取一遍模，由于模运算的性质，这并不会影响结果。（a+b）%mod==( a%mod+b%mod )%mod。
可以先取排序之后的最后两个数，如果他们的和小于模p，直接输出他们的和，因为这一定是最大的。
否则的话还得找，设置 l 从0开始往后，r从n-1开始往前，对于每个 l ，找到最右边的r，使得a[ l ]+a[ r ]<p,
这时r就不用往前了，因为往前的话值一定会变小，每次找到之后，更新最大值，同时 l 往前一位，但是 r 不用动，
因为数组是有序的，（仔细想想就知道了），这样时间复杂度就控制在线性阶了。
另外2^31-1是2147483647，有符号整型能表示的最大值.
#include<map>#include<vector>#include<cstdio>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<stack>#include<queue>#include<set>#define inf 0x3f3f3f3f#define mem(a,x) memset(a,x,sizeof(a))using namespace std;typedef long long ll;typedef pair<int,int> pii;inline ll in(){ll res=0;char c;while((c=getchar())<'0' || c>'9');while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();return res;}ll a[100010];int main(){int n,p;while(~scanf("%d%d",&n,&p)){for(int i=0;i<n;i++){a[i]=in()%p;}sort(a,a+n);//排序ll mx=(a[n-1]+a[n-2])%p;int l=0,r=n-1;while(l<r){while(r>=0 && a[l]+a[r]>=p)r–; //防止r<0if(l<r) mx=max(mx,a[l]+a[r]); //r不能小于等于ll++;}cout<<mx<<endl;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
你说，你可以把它取下来吗？当我要取的时候，你淘气的躲开了，
