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,n1000).

For each case: 

The following line contains two integers,n(2n100000)p(1p2311)

The following line contains n integers ai(0ai2311)

 

 

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)了
这个优化前几天刚遇到过。。。。
 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz