题解：P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

Milk_Dragon · 2024-07-22 19:32:42 · 个人记录

提供一个不一样的做法。

思路：

众所周知，这题每合并一次就排序一次会超时，所以我们不排序不进行完全的排序。

我们可以在第一次合并前先排一次，这样每次合并后只需对合并后的数进行冒泡，遇到比它小的就交换，遇到比它大的就停止，因为后面的数已经有序了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=20000+5;
int n,a[N],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n-1;i++){
        ans+=a[i]+a[i+1];
        int c;
        c=a[i]+a[i+1];
        a[i+1]=c;
        for(int j=i+1;j<=n-1;j++){
            if(a[j]>a[j+1]){
                swap(a[j+1],a[j]);
            }
            else break;
        }
    }
    cout<<ans;
    return 0;
}