[TIOJ] 1610. Problem D 搭橋 (BRIDGE)

題目連結:http://tioj.infor.org/problems/1610

---

乍看之下還以為是什麼奇怪的樹題，結果其實是個簡單的greedy題。
應該不難看出我們其實可以把船亂排、木板亂排，而答案會是$\sum_{i=0}^{n-1} L_i \sum_{j=0}^{i} W_j$，稍微觀察後會發現其實我們由小拿到到，然後木板由長的接到短的會是好的，因為你若拿了比較多再走長的一定會消耗較多體力。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 20000 + 5;

lld arr[N], woo[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	for(int i=1;i<n;i++) cin>>woo[i];
	sort(arr, arr+n);
	sort(woo+1, woo+n, [](lld a, lld b){return a>b;});
	lld cur = arr[0], ans = 0;
	for(int i=1;i<n;i++){
		ans += cur*woo[i];
		cur += arr[i];
	}
	cout<<ans<<'\n';
	return 0;
}