自动搬运

查看原文

来自洛谷，原作者为

	Night_sea_64 距离省选还有 +inf 天。

搬运于2025-08-24 22:45:55，当前版本为作者最后更新于2023-03-23 20:37:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

如果 $T$ 是 $S$ 的真子集，则 $T$ 是由 $S$ 删除至少一个元素得到的。

容易发现，这题集合中的元素都是正整数，所以我们加上一个元素一定会使元素和更大，所以第一问的答案一定是 $n-1$。

我们肯定需要让 $T$ 恰好是 $S$ 删除一个元素得到的，而且删除的数需要尽量小才可以保证和最大。

而我们通过 “对于 $T$ 中的每一个元素 $i$，要么 $i$ 在 $S$ 中没有前驱，要么 $i$ 在 $S$ 中的前驱 $\in T$。” 这句话可以看出，一个 $S$ 中的元素 $x$ 可以不在 $T$ 中需要满足下面两个条件之一：

1. $x$ 是 $S$ 中最大值。这样的话就不会有元素的前驱是 $x$ 了。
2. $x$ 在 $S$ 中出现不止一次，并且在 $T$ 中出现至少一次。这样的话如果有元素的前驱是 $x$，也会在 $T$ 中出现。

然后我们就找 $S$ 中满足这两个条件之一的最小的元素删掉就可以了。注意开 long long。

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[100010];
int main()
{
    cin>>n;
    long long s=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s+=a[i];
    }
    sort(a+1,a+n+1);
    bool flag=0;
    for(int i=1;i<=n;i++)
        if(a[i]==a[i-1])
        {
            flag=1;
            s-=a[i];
            break;
        }
    if(!flag)s-=a[n];
    cout<<n-1<<" "<<s<<endl;
    return 0;
}