归并排序 and 贪心 and 小型的插入排序 = =

blue_point · 2019-12-03 22:23:02 · 个人记录

这个题做了好久才做出来。主要是之前不会归并排序，只会用sort。这个题如果用sort会超时。甚至单纯用归并也会超时（没试过）。因为每一次贪心都需要找到最轻的两个果子，因此每一次合并果子都需要排序。这种局部变化，整体不变的，比较适合插入排序。

因此只需要一开始归并排一次，之后每一次合并果子都进行一次局部的插入排序 = v = 加油！

#include <iostream>
#include <algorithm>
using namespace std;
int arr[10001];
void MERGE(int arr[],int head,int mid,int tail,int temp[]){
    if(head == tail)return;
    int lf = head , rf = mid + 1;
    int cnt = 0;
    while(lf <= mid and rf <= tail){
        if(arr[lf] <=arr[rf] )temp[cnt++] = arr[lf++];
        else temp[cnt++] = arr[rf++];
    }
    while(lf <= mid)temp[cnt++]=arr[lf++];
    while(rf <=tail)temp[cnt++]=arr[rf++];
    for(int i = 0; i < cnt; i++){
        arr[head + i] = temp[i];
    }
}
void MERGE_SORT(int arr[],int head,int tail,int temp[]){
    if(head < tail){
        int mid = (head + tail)/2;
        MERGE_SORT(arr,head,mid,temp);
        MERGE_SORT(arr,mid+1,tail,temp);
        MERGE(arr,head,mid,tail,temp);
    }
    return;
}
void CHANGE(const int start,const int m,int arr[],const int len){
    int i = start;
    while(arr[i] <= m and i <len ){
        arr[i-1] = arr[i];
        i++;
    }
    arr[i-1] = m;return;
}
int temp[20000];
int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    MERGE_SORT(arr,0,n-1,temp);
    int ANS = 0;
    for(int i = 0; i <= n-2; i++){
        int sum = arr[i]+arr[i+1];
        CHANGE(i+1,sum,arr,n);
        ANS += sum;
    }
    cout << ANS;
}