pog loves szh II
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 459 Accepted Submission(s): 123
Problem Description Pog and Szh are playing games.There is a sequence with n 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 (A+B) mod p .They hope to get the largest score.And what is the largest score?
Input Several groups of data (no more than 5 groups, n≥1000 ).
For each case:
The following line contains two integers, n(2≤n≤100000) , p(1≤p≤231−1) 。
The following line contains n integers ai(0≤ai≤231−1) 。
Output For each case,output an integer means the largest score.
Sample Input
4 4
1 2 3 0
4 4
0 0 2 2
Sample Output
3
2
Source BestCoder Round #43 原文地址
官方题解:
<span style="font-size:18px;">#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 100010;
LL a[MAXN];
int main()
{
int n, p;
while (cin >> n >> p)
{
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
a[i] %= p;
}
sort(a, a+n);
LL ans = (a[n-1]+a[n-2])%p;
int i = 0, j = n-1;
while (i < j)
{
if (a[i] + a[j] >= p)
--j;
else
{
ans = max(ans, a[i]+a[j]);
++i;
}
}
cout << ans << endl;
}
return 0;
}</span>
搜索
复制