[GDCPC2023] New Houses 详细题解

· · 题解

题目大意

有 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;
    }
}