CF1690(Div3) E. Price Maximization 好题

题目传送门

首先，可以发现，我们不关心原数字的大小，只关心他们除以 \(k\) 之后的余数。如此考虑： 两个数相加，\((a + b) / k = a / k + b / k + (a\) \(mod\) \(k + b\) \(mod\) \(k) / k\)。
如果二者余数部分达不到 \(k\)，那么相加时其余数也必然不会对总答案有效。

因此，直接对每个数取余，然后判断所有余数中有多少对能相加大于等于 \(k\)。

思路非常好的一道题。

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

int a[N]; 
int main(){
  // freopen("hh.txt", "r", stdin); 
  int T; read(T);
  while(T--){
    int n, k; 
    read(n), read(k);
    for(int i = 1; i <= n; i++) read(a[i]); 
    ll ans = 0; 
    for(int i = 1; i <= n; i++){
      ans += a[i] / k; 
      a[i] %= k; 
    }
    sort(a + 1, a + n + 1); 
    int l = 1, r = n; 
    for( ; l < r; l++, r--){
      while(a[l] + a[r] < k && l < r) l++; 
      if(l >= r) break; 
      ans++; 
    }
    printf("%lld\n", ans); 
  }
  return 0;
}