长安大学 迎新赛 圣诞节分糖果问题

做法，我们将所有值先取余一下p， 最后的得到的值，分为了两部分，a+b相加都大于等于p，相加一定小于p

分别求出这两部分的最大值，然后进行比较大小. 可以确定地是 1.大于等于p的部分随着两个糖果数的增大，答案也会增大 因为ans=p-(t1+t2) t1=a1%p,t2=a2%p a1,a2取不大于p的最大值，那么t1,t2得到的就是最小值，最后得到的大于等于p部分的ans得到的 就是最大值。 第二部分a1,a2相加的结果总是小于p的部分我们通过a[l]+a[r]<p中得到满足条件的最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,p;
        cin>>n>>p;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            a[i]=x%p;
        }
        sort(a,a+n);
        int ans=(a[n-2]+a[n-1])%p;//开始值为>=p的部分最大的值，他一定是最大的。
        int l=0,r=n-1;
        while(l<r){
            while(a[l]+a[r]>=p) r--;//把范围缩小相加<p的部分
            if(l<r){
                ans=max(ans,a[l]+a[r]);
                l++;//增大a1看看是否会得到更大的值
            }
        }
        cout<<ans<<endl;
    }

return 0;

}