bc #43(hdu 5265) pog loves szh II （单调性优化）
pog loves szh II
**Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2115 Accepted Submission(s): 609
**
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
Recommend
hujie | We have carefully selected several similar problems for you: 5338 5337 5336 5335 5334
对于读入的a[i] mod p后
对于任意 0=
所以a[i]+a[j]的结果只有两种情况，一种是 =p <=2p-2 a[i]+a[j]-p 是答案
把a[i]升序排列，如果存在a[i]+a[j]>=p ,那么最大的一定是a[n-1]+a[n-2]
对于a[i]+a[j]小于p的，我们枚举i，找到最大的j，使得a[i]+a[j]
如果直接枚举O(N2)会超时
由于a[i]数组已经是有序的了
我们可以利用a[i]的单调性，从两边往中间找。
这样复杂度就是O(N)了
这个优化前几天刚遇到过。。。。
1/*************************************************************************
2 > File Name: code/bc/#43/B.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年07月31日 星期五 16时38分13秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int N=1E5+7;
32LL a[N];
33int n,p;
34
35int main()
36{
37 while (scanf("%d %d",&n,&p)!=EOF)
38 {
39 LL ans = -1;
40 for ( int i = 0 ; i < n; i++ )
41 {
42 scanf("%lld",&a[i]);
43 a[i]=a[i]%p;
44 }
45 sort(a,a+n);
46 ans = (a[n-1]+a[n-2])%p;
47 int j = n-1;
48 for ( int i = 0 ; i < n-2 ; i++ )
49 {
50 while (i<j&&a[i]+a[j]>=p) j--;
51 ans = max(ans,(a[i]+a[j])%p);
52 }
53 cout<<ans<<endl;
54
55 }
56
57 return 0;
58}