自动搬运

查看原文

来自洛谷，原作者为

	I_am_AKed_by_NOI 数学里有一个虐心的事实：两条平行线永不相交。两条相交的线，先是不停相近，但在经历唯一的相交后，越离越远。

搬运于2025-08-24 22:50:52，当前版本为作者最后更新于2023-10-13 23:30:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

有 $n$ 个居民，住进 $m$ 个排成一排的房子。若第 $i$ 个居民有邻居，分数增加 $a_i$，反之有邻居，分数增加 $b_i$。找到是分数最大的一居住方式，并输出分数。

正解

因为要找到最大的分数，可以考虑动规，发现不可行，转换思路，考虑贪心。

我们首先假设每个人都没有邻居，那么幸福指数的总和即为 $\sum\limits_{i=1}^{n} b_i$。如果我们让第 $i$ 个人拥有邻居，那么这个总和将会增加 $a_i-b_i$。为了让总和最大，所以增加的 $a_i-b_i$ 也要尽量的大，于是我们以 $a_i-b_i$ 的值从大到小给数组排序。

数组经过排序后，我们思考如何计算 $x$ 个人拥有邻居时幸福总和最大值为多少。针对这个问题，我们可以让排序后数组中的前 $x$ 个人挨在一起，这样会使得幸福值的总和最大。

此时，总和会增加 $\sum\limits_{i=1}^{x} (a_i-b_i)$ 的幸福值。那么总和就为

$$\sum\limits_{i=1}^{n} b_i + \sum\limits_{i=1}^{x} (a_i-b_i)=\sum\limits_{i=1}^{n} b_i + \sum\limits_{i=1}^{x} a_i- \sum\limits_{i=1}^{x}b_i=(\sum\limits_{i=1}^{n} b_i- \sum\limits_{i=1}^{x}b_i) + \sum\limits_{i=1}^{x} a_i=\sum\limits_{i=x+1}^{n} b_i + \sum\limits_{i=1}^{x} a_i $$

这里显然可以使用前缀和来优化复杂度。所以我们枚举每一个 $x$，计算最大的总和，更新答案。同时，这里要注意 $x$ 的合法性。什么意思呢，如果有 $x$ 个人要有邻居，房间数最少需要 $x+2\times(n-x)$，所以在枚举 $x$ 的过程中，要判断 $x+2\times(n-x) \le m$，否则不执行计算和更新。

代码

注意！！！这不是 AC 代码！！！！

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node
{
	int a;
	int b;
}data[N];
int sum1[N],sum2[N],ans;
int T,n,m;
bool cmp(node x1,node x2) //以 a_i - b_i 从大到小排序 
{
	return x1.a-x1.b>x2.a-x2.b;
}
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>data[i].a>>data[i].b;
		sort(data+1,data+n+1,cmp); //贪心，将数组排序 
		for(int i=1;i<=n;i++)
		{
			sum1[i]=sum1[i-1]+data[i].a; //a 的前缀和 
			sum2[i]=sum2[i-1]+data[i].b; //b 的前缀和 
		}
		2*n-1<=m?ans=sum2[n]:ans=0;
		for(int x=2;x<=n;x++) //枚举 x 
		{
			if(2*n-x<=m) //判断是否合法 
			{
				ans=max(sum1[x]+sum2[n]-sum2[x],ans); //计算答案同时更新 
			}
		}
		cout<<ans<<endl;
	}
} 

十年 OI 一场空，不开 long long 见祖宗！！！

下面是 AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
struct node
{
	ll a;
	ll b;
}data[N];
ll sum1[N],sum2[N],ans;
ll T,n,m;
bool cmp(node x1,node x2) //以 a_i - b_i 从大到小排序 
{
	return x1.a-x1.b>x2.a-x2.b;
}
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>data[i].a>>data[i].b;
		sort(data+1,data+n+1,cmp); //贪心，将数组排序 
		for(int i=1;i<=n;i++)
		{
			sum1[i]=sum1[i-1]+data[i].a; //a 的前缀和 
			sum2[i]=sum2[i-1]+data[i].b; //b 的前缀和 
		}
		2*n-1<=m?ans=sum2[n]:ans=0;
		for(int x=2;x<=n;x++) //枚举 x 
		{
			if(2*n-x<=m) //判断是否合法 
			{
				ans=max(sum1[x]+sum2[n]-sum2[x],ans); //计算答案同时更新 
			}
		}
		cout<<ans<<endl;
	}
}