[TIOJ 1225] 數字合併

作法：

greedy，考慮最小的那個數，看看他的左右，會發現這兩個數一定大於等於他(廢話)(當然如果在邊界那就只有一個)，直覺會認為選其中一個比較小的然後用他把這個數砍掉是最好的。主要是因為，假設砍掉 ai 的數在他右邊但不和他相鄰好了，那他必須能夠砍掉 ai 右邊的那個數，才有機會來到 ai 的旁邊，也就是他 >= ai 右邊的數，這樣花費會變高，所以不如早點用 ai 右邊的把他砍掉還要好。

而實作上需要「砍掉一個數」和「詢問一個數的左右是誰」，所以用 linked list 。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
struct P
{
    int id,val ;
    bool operator < (const P &rhs) const
    {
        return val>rhs.val ;
    }
};
 
int a[maxn],ri[maxn],le[maxn] ;
priority_queue<P> pq ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]) ,
        le[i]=i-1 , ri[i]=i+1 ,
        pq.push((P){i,a[i]}) ;
    LL ans=0LL ;
    while(pq.size()>1)
    {
        P u=pq.top() ; pq.pop() ;
        if(!le[u.id]) { ans+=a[ri[u.id]] ; le[ri[u.id]]=0 ; continue ; }
        if(ri[u.id]==n+1) { ans+=a[le[u.id]] ; ri[le[u.id]]=n+1 ; continue ; }
        ans+=min(a[le[u.id]],a[ri[u.id]]) ;
        le[ri[u.id]]=le[u.id] ;
        ri[le[u.id]]=ri[u.id] ;
    }
    printf("%lld\n",ans) ;
}