6.26cf simulation race e: solution to the problem of price maximization

Title Description

link

CF Simulation game E： Price maximization solution

A word description

E. Price maximization
time limit per test2 s.
memory limit per test256 MB
inputstandard input
outputstandard output
A batch of n goods (n — an even number) is brought to the store, i-th of which has weight ai. Before selling the goods, they must be packed into packages. After packing, the following will be done:

There will be n2 packages, each package contains exactly two goods;
The weight of the package that contains goods with indices i and j (1≤i,j≤n) is ai+aj.
There is stock in the store n (n It's even ) Commodity , The first i The weight of each piece is ai. Before selling , Goods need to be packed ：

All items will be marked as n2 Parcel , Each package happens to contain 2 Commodity ;
If a package contains The first i and The first j (1≤i,j≤n) Commodity , Then the weight of this package is ai+aj.
With this, the cost of a package of weight x is always ⌊xk⌋ burles (rounded down), where k — a fixed and given value.

One weighs x Package , price is ⌊xk⌋ （ Round down ）, among k Is a given value .

Pack the goods to the packages so that the revenue from their sale is maximized. In other words, make such n2 pairs of given goods that the sum of the values ⌊xik⌋, where xi is the weight of the package number i (1≤i≤n2), is maximal.

How to package to maximize the total profit ？ let me put it another way , Combine products n2 Yes , bring ⌊xik⌋ The sum of the Maximum , among xi yes The first i (1≤i≤n2) The weight of a package .

For example, let n=6,k=3, weights of goods a=[3,2,7,1,4,8]. Let’s pack them into the following packages.

In the first package we will put the third and sixth goods. Its weight will be a3+a6=7+8=15. The cost of the package will be ⌊153⌋=5 burles.
In the second package put the first and fifth goods, the weight is a1+a5=3+4=7. The cost of the package is ⌊73⌋=2 burles.
In the third package put the second and fourth goods, the weight is a2+a4=2+1=3. The cost of the package is ⌊33⌋=1 burle.
With this packing, the total cost of all packs would be 5+2+1=8 burles.

for example , hypothesis n=6,k=3, The weight of the goods is a=[3,2,7,1,4,8]. We pack it as follows ：

The first package contains 3 and The first 6 Commodity . Then the package weight is a3+a6=7+8=15. price is ⌊153⌋=5.
The second package contains 1 and The first 5 Commodity . Then the package weight is a1+a5=3+4=7. price is ⌊73⌋=2.
The third package contains 2 and The first 4 Commodity . Then the package weight is a2+a4=2+1=3. price is ⌊33⌋=1.
The total price of all packages is 5+2+1=8.

Input
The first line of the input contains an integer t (1≤t≤104) —the number of test cases in the test.

The first line contains an integer t (1≤t≤104) — Number of representative test data groups .

The descriptions of the test cases follow.

The following describes each test data .

The first line of each test case contains two integers n (2≤n≤2⋅105) and k (1≤k≤1000). The number n — is even.

The first line contains two integers n (2≤n≤2⋅105) and k (1≤k≤1000).n It's even .

The second line of each test case contains exactly n integers a1,a2,…,an (0≤ai≤109).

The second line contains n It's an integer a1,a2,…,an (0≤ai≤109).

It is guaranteed that the sum of n over all the test cases does not exceed 2⋅105.

Data guarantees the accuracy of all test data n The sum does not exceed 2⋅105.

Output
For each test case, print on a separate line a single number — the maximum possible total cost of all the packages.

For each set of data , Output an integer representing the maximum price .

Example
inputCopy
6
6 3
3 2 7 1 4 8
4 3
2 1 5 6
4 12
0 0 0 0
2 1
1 1
6 10
2 0 0 5 9 4
6 5
5 3 8 6 3 2
outputCopy
8
4
0
2
1
5
Note
The first test case is analyzed in the statement.

For the first example , The problem has been analyzed in the description .

In the second test case, you can get a total value equal to 4 if you put the first and second goods in the first package and the third and fourth goods in the second package.

For the second example , We can pack the first and second items 、 The third and fourth items are packed , The total price can reach 4.

In the third test case, the cost of each item is 0, so the total cost will also be 0.

For the third example , The value of each package is 0, So the total value is 0.

Topic analysis

1. The subject data is very complex, so we should simplify and reduce the scale of the small problem first
2. Mainly use mathematical thinking to divide , All numbers /k Sum the numbers rounded down , There must be .
3. Save the remainder
4. The local optimal solution will be greedy i and k-i Gather together
5. Next, from the remaining maximum number and the minimum number that can be counted with him

Code implementation

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

const int maxn=2e5+10;
int t,n,k,x;
ll ans;
int cnt[1000+10];
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		ans=0;
		memset(cnt,0,sizeof(cnt));
		scanf("%d%d",&n,&k);
		// Remainder record  
		for(int i=1;i<=n;i++){
    
			scanf("%d",&x);
			ans=ans+x/k;
			cnt[x%k]++;		
		}
		//printf("%d\n",ans);
		// The first round  
		for(int i=1;i<=k/2;i++){
    
			if(cnt[i]==0)continue;
			if(i+i==k){
    
				ans=ans+cnt[i]/2;
				cnt[i]%=2;
				break;
			}
			int op=min(cnt[i],cnt[k-i]);
			ans=ans+op;
			cnt[i]=cnt[i]-op;
			cnt[k-i]=cnt[k-i]-op;
		}
		//printf("%d\n",ans);
		// The second round  
		for(int i=k-1;i>=1;i--){
    
			if(cnt[i]==0)continue;
			for(int j=1;j<=i;j++){
    
				if(cnt[i]==0||cnt[j]==0)continue;
				if(i+j>k){
    
					if(i==j){
    
						//printf("%d\n",cnt[i]);
						ans=ans+cnt[i]/2;
						cnt[i]%=2;
						continue;
					}
					int op=min(cnt[i],cnt[j]);
					ans=ans+op;
					cnt[i]=cnt[i]-op;
					cnt[j]=cnt[j]-op;
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}