ACM学习历程—HDU5265 pog loves szh II（策略 && 贪心 && 排序）

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 \geq 1000$).
For each case:
The following line contains two integers,$n(2 \leq n \leq 100000)$，$p(1 \leq p \leq 2^{31}-1)$。
The following line contains $n$ integers $a_i(0 \leq a_i \leq 2^{31}-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

首先对所有的数模p再排序是没有问题的。

然后就是怎么求模p的最大值。

首先如果a[n-2]+a[n-1]小于p，自然最大值就是它。

然而打BC的时候并没有考虑透彻，然后想对最大值进行枚举，看能不能凑到这个最大值，因为直接暴力枚举会T，然后想二分，但是貌似不能直接二分，于是我还是设了一个左值lt和右值rt，rt自然初始为p-1，而lt初始值可以取a[0]+a[n-1]和a[n-2]+a[n-1]里面较大的。然后就是如果mid值能凑到，自然更新lt为mid值，然后判断rt能否取到，否则自减，然而这样是过不了极限数据的。不过貌似OJ测试数据并没有，这样是可以过的。。。不过当时没考虑int爆掉，还有二分也写搓被Hack掉了。

然后就是正规做法了：

考虑到之前模过后进行的排序，所以任意两个数相加的和比p大的值要小于p，所以减一次就能比p小，所以最大值只有两种可能，x+y或x+y-p。

然后对于后者，最大自然是a[n-2]+a[n-1]-p（在得到它们和大于p的前提下），然后只用找x+y的最大了。

然后从小到大枚举每个x，y自然是从大到小排除，得到首个比p小的。

由于对于x+c来说，x+c+y > x+y，所以，如果之前x+y超过p的，x+c+y自然也超过p了。所以往后的y不需要返回继续减小即可。

暴力枚举代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long

using namespace std;

int n;
LL s[100010], p;

inline Max(LL x, LL y)
{
    if (x < y)
        return y;
    else
        return x;
}

void Input()
{
    for (int i = 0; i < n; ++i)
    {
        scanf("%I64d", &s[i]);
        s[i] %= p;
    }
    sort(s, s+n);
}

int binarySearch(LL key)
{
    int lt = 0, rt = n-1, mid;
    while (lt <= rt)
    {
        mid = (lt+rt) >> 1;
        if(key == s[mid])
            return mid;
        if(key < s[mid])
            rt = mid-1;
        if(key > s[mid])
            lt = mid+1;
    }
    return -1;
}

bool judge(LL k)
{
    for (int i = 0; i < n; ++i)
    {
        if (k-s[i] >= 0 && binarySearch(k-s[i]) != -1)
            return true;
        if (k-s[i] <= 0 && binarySearch(k-s[i]+p) != -1)
            return true;
    }
    return false;
}

void Work()
{
    LL maxs = s[n-2]+s[n-1];
    if (maxs < p)
    {
        printf("%I64d\n", maxs);
        return;
    }
    LL lt = Max((s[0]+s[n-1])%p, (s[n-2]+s[n-1])%p), rt = p-1, mid;
    while (lt < rt)
    {
        mid = (lt+rt) >> 1;
        if (judge(mid))
            lt = mid;
        if (judge(rt))
        {
            printf("%I64d\n", rt);
            return;
        }
        else
            rt--;
    }
    printf("%I64d\n", lt);
}

int main()
{
    //freopen("test.in", "r", stdin);
    while (scanf("%d%I64d", &n, &p) != EOF)
    {
        Input();
        Work();
    }
    return 0;
}

View Code

正确代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define LL long long

using namespace std;

int n;
LL p, a[100005];

void Input()
{
    for (int i = 0; i < n; ++i)
    {
        scanf("%I64d", &a[i]);
        a[i] %= p;
    }
    sort(a, a+n);
}

void Work()
{
    LL maxs = a[n-1]+a[n-2];
    if (maxs < p)
    {
        printf("%I64d\n", maxs);
        return;
    }

    maxs -= p;
    int lt = 0, rt = n-1;
    while (lt < rt)
    {
        while (a[lt]+a[rt] >= p && lt < rt)
            rt--;
        if (lt >= rt)
            break;
        maxs = max(maxs, a[lt]+a[rt]);
        lt++;
    }
    printf("%I64d\n", maxs);
}

int main()
{
    //freopen("test.in", "r", stdin);
    while (scanf("%d%I64d", &n, &p) != EOF)
    {
        Input();
        Work();
    }
    return 0;
}

View Code

ACM学习历程—HDU5265 pog loves szh II（策略 && 贪心 && 排序）

推荐阅读