列表

详情

NC252836. Evil Capitalist

描述

Today Colin and Eva learned what is exploitation in the course 'Basic Principles of Marxism'. At night, Colin had a dream where he was a poor worker, cruelly exploited by capitalist Eva without realizing it at all...
Assuming you are an evil capitalist with n exploited workers under your command, numbered from 1 to n . The current salary of worker with number i is a_i yuan. Under your strict supervision, workers cannot tell each other their salaries. You thought the good days would continue like this, but the workers increasingly felt exploited, so they decided to strike and protest against you!

Without the labor of workers, there wouldn't be a luxurious life for you. So you decide to raise their salaries in an appropriate way to stop them from protesting. At first, every worker is unsatisfied. You need to organize several two-person chats to make everyone satisfied, or only one person unsatisfied - at this point, there will be nobody who wants to protest against you with him.

To organize a two-person chat, you need to choose two unsatisfied workers x,y , then allow them to tell each other their salaries without penalty temporarily:
But as an evil capitalist, you want to know at least how much money you need to pay them to achieve your goal.

输入描述

The first line contains one integer n \ (1 \le n\le 2\times 10^5) , representing the number of workers.

The second line contains n integers a_1,a_2,\dots,a_n\ (1\le a_i\le 10^9) ; a_i represents the current salary of the i-th worker.

输出描述

A single integer, represents the minimum amount of money you need to spend.

示例1

输入: 

4
100 101 1 101

输出: 

1

说明:

You can first let worker 1 talk with worker 2 , then worker 2 will become satisfied, and you need to pay 1 yuan to worker 1 , then a_1 becomes 101 .

Then you can let worker 1 talk with worker 4 , since they have the same salary, so both of them will become satisfied.

Then only the worker 3 is not satisfactory, you have already achieved your goal.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 112ms, 内存消耗: 2032K, 提交时间: 2023-07-31 23:49:43 

#include <bits/stdc++.h>
using namespace std;
long n,sum,mx,cnt,now,a[200001],i;
int main()
{
	cin>>n;
	while(i<n) cin>>a[i++];
	sort(a,a+n);
	a[n]=2e9;
	for(i=0;i<n;i++){
		if(a[i]==a[i+1]) cnt++;
		else{
			now=cnt%2?0:a[i+1]-a[i];
			sum+=now;
			mx=max(mx,now);
			cnt=0;
		}
	}
	cout<<sum-mx;
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 106ms, 内存消耗: 2112K, 提交时间: 2023-07-14 00:03:18 

#include <bits/stdc++.h>
using namespace std;
long n,sum,mx,cnt,now,a[200001],i,j;
int main()
{
	cin>>n;
	while(j<n) cin>>a[j++];
	sort(a,a+n);
	a[n]=2e9;
	for(;i<n;i++){
		if(a[i]==a[i+1]) cnt++;
		else{
			now=cnt%2?0:a[i+1]-a[i];
			sum+=now;
			mx=max(mx,now);
			cnt=0;
		}
	}
	cout<<sum-mx;
	return 0;
}

上一题

© 2025 nowcoder.com