当前位置: 代码迷 >> 综合 >> HDOJ 5265 pog loves szh II
  详细解决方案

HDOJ 5265 pog loves szh II

热度:89   发布时间:2023-12-06 03:27:00.0

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5265

题意很简单,给我们n个数,和一个p,从n个数中取两个数A和B,问我们能够得到的最大的(A+B)%p为多少。

这道题我们可以用贪心过,首先先对每个数取余,我们贪心的策略就是枚举每一位x,看能不能找到一个值比p-x-1相等或小的值,找到最大的这个值,如果没有,说明找不到一个数和它相加小于p,那么直接加最大的那个数。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL __int64
using namespace std;
const int maxn = 100005;
LL a[maxn],p;
int n;
void read(LL &x)
{int flag = 0;x = 0;char c = getchar();if(c == '-') flag = 1;while(c<'0' || c>'9'){if(c == '-') flag = 1;c = getchar();}while(c >= '0' && c <= '9')x = x*10+c-'0', c = getchar();if(flag) x = -x;
}
int main()
{while(scanf("%d%I64d",&n,&p) !=EOF){for(int i=0; i<n; i++){read(a[i]);a[i] %= p;}sort(a,a+n);LL ans = (a[n-1]+a[n-2])%p;//for(int i=0; i<n; i++) printf("%d ",a[i]);for(int i=0; i<n-1; i++){LL mod = p-a[i]-1;int pos = upper_bound(a, a+i-1, mod)-a-1;if(pos == -1) ans = max(ans, (a[i]+a[n-1])%p);else ans = max(ans, (a[i]+a[pos])%p);}printf("%d\n",ans);}
}