hdu 5265 pog loves szh II STL

pog loves szh II

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5265

Description

pog在与szh玩游戏，首先pog找到了一个包含n个数的序列，然后他在这n个数中挑出了一个数A，szh出于对pog的爱，在余下的n−1个数中也挑了一个数B，那么szh与pog的恩爱值为(A+B)对p取模后的余数，pog与szh当然想让恩爱值越高越好，并且他们想知道最高的恩爱值是多少。

Input

若干组数据(不超过5组n≥1000)。
每组数据第一行两个整数n(2≤n≤100000)，p(1≤p≤231−1)。
接下来一行n个整数ai(0≤ai≤231−1)。

Output

对于每组的每个询问，输出一行，表示pog与szh的最大恩爱值。

Sample Input

4 4
1 2 3 0
4 4
0 0 2 2

Sample Output

3
2

HINT

题意

题解：

STL大法好！

STL拯救世界！

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 2000001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

ll a[maxn];

multiset<ll> S;

int main()

{

    //test;

    int n;

    ll p;

    while(cin>>n>>p)

    {

        S.clear();

        for(int i=;i<n;i++)

        {

            a[i]=read();

            a[i]%=p;

            S.insert(a[i]);

        }

        ll ans=;

        for(int i=;i<n;i++)

        {

            S.erase(S.find(a[i]));

            multiset<ll>::iterator it=S.lower_bound(p-a[i]);

            it--;

            ans=max(ans,(a[i]+*it)%p);

            it=S.lower_bound(p*-a[i]);

            it--;

            ans=max(ans,(a[i]+*it)%p);

            S.insert(a[i]);

        }

        cout<<ans<<endl;

    }

}