P9160 题解

Night_sea_64 · 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 中需要满足下面两个条件之一：

然后我们就找 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;
}