P8297题解

lihanwen12 · 2022-04-25 12:03:23 · 题解

题目大意
给定 n 个链，每个链由若干个相邻的节构成，可以通过一次操作将一个节打开使其充当粘合剂的作用能连上两个链，求最少操作次数。

解题思路
一种将所有链连在一起的可行操作显然是每个链的末尾节打开和下一个链的开头节连在一起，这样做的操作次数是 n-1，不符合第二个样例和第三个样例。观察发现样例二把第 1 个链只有 1 个节，打开这个节以后需要连在一起的链只剩下后 2 个了，样例三打开了最小的长度为 3 的链条的所有节，打开这些节后最小的链条不复存在，剩下的 4 个链条只需要 3 个已打开的节去粘合了。
提出贪心策略：既然注定要有部分节被打开成为若干链条之间的粘合剂，我们可以让需要粘合的链条数目尽可能地少。对所有链条以长度为关键字从小到大进行排序，优先拆散长度短的链条的节，全拆以后会使得需要粘合的链条数目减少 1。看看这些已经被打开节能不能满足剩余完整的较长链条的粘合需求，还要考虑一下当前链不用全部打开就能满足后面需求的情况。

代码

#include<bits/stdc++.h>
using namespace std;
long long read(){
    long long x=0,sgn=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')sgn=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
    return x*sgn;
}
long long n,ans,a[500010],sum;
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+n+1);
    ans=n-1;//先全部首尾相连在一起 
    for(int i=1;i<=n;i++){
        sum+=a[i];
        //(n-i-1)为后面所需粘合剂的数量
        if(sum==n-i-1){//恰好相等，样例 3 所示情况 
            ans=min(ans,sum);
            break;
        }
        if(sum>n-i-1){//不用全拆，需求粘合剂个数 +1 
            ans=min(ans,n-i);
            break; 
        }
    }
    printf("%lld",ans);
    return 0;
}