UESTC 1263 The Desire of Asuna 贪心法&&构造法

首先，如果都很大1，则n-1次。如果一个1则可以减少1次，但如果有一个2，则拆开后如果都可以用上，则也可以减少一次，其它的也是这样。
那么凑出足够的1，来连接链，即可。
○ 1 ○ 1○ 1○ 1 ○ 1○ 1 ○ 且最后结束的时候必然是这样还剩余的链刚好被那些1连接。
贪心策略：先排序，从最小的开始搞，取环凑1。(每取出or凑出一个1消耗一个代价)
如果 a[i]==0, 则 i++，len-- (剩余的链数 -- )；//最后恰好剩余的链中，最前面的那个链是1也不要紧，它还是作为一个链○处理
如果 a[i]!=0, a[i]--,cot++ (已凑出的1的个数 ++ );
当满足 ○ 1 ○ 1 ○ 1 ○ 1 ○ 1 ○ 1 ○，即cot==len-1时结束。代价为cot。

#include 
#include 
#include 
const int maxn=2004;
int a[maxn];
using namespace std;

int main()
{
    int n,cot=0,len;
    scanf("%d",&n);len=n;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);int i=0;
    while(cot!=len-1){
        if(a[i]!=0) {a[i]--;cot++;}
        else {i++;len--;}
    }
    printf("%d",cot);
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx