CF1690E Price Maximization

题意

我们有 \(n\) 个礼物，而最终我们需要将所有的礼物两两包成 \(\frac{n}{2}\) 个包裹。

每一个礼物 \(i\) 都有其价值 \(a_i\)，而含有礼物 \(i\) 与礼物 \(j\) 的包裹的价值是 \(\lfloor \frac{a_i+a_j}{k} \rfloor\)。

我们需要找出一个方案来使得所有包裹的价值之和最大，并求出这个最大值。

思路

很明显，对于所有\(i\in [1,n]\)，都有\(a_i=k\times q_i+r_i(r_i<k)\)，其中\(k\)的意思如题

那么，这\(n\)个数的两两包成一个后的重量就是\(\lfloor \frac{q_i+r_i+q_j+r_j}{k}\rfloor\)，而如果把他们相加后，只有\(r_i,r_j\)的值会影响最重的重量，也就是说这个式子是一定的：

\[最小重量=\sum_q^{i=1}\times \frac{1}{k} \]

而如果想让他变得更大，就要让每一对\(r_i+r_j\)都尽量大于\(k\)，这里可以用双指针挨个找

即，如果\(r_l+r_r<k\)，那么\(l+1\)，否则这一对就且定下来了，最后的重量就又加一

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
int n,k,ans;
int a[Maxn];
void run()
{
	cin>>n>>k;ans=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		ans+=a[i]/k;
		a[i]%=k;
	}
	sort(a+1,a+n+1);
	int l=1,r=n;
	while(l<r)
	{
		if(a[l]+a[r]>=k) ans++,r--;
		l++;
	}
	cout<<ans<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--) run(); 
}