[TIOJ] 1329. 交換數字

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

---

裸裸的$O(n^2)$做，算一下交換後是否有變少即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;
typedef pair<int,int> PII;
#define FF first
#define SS second

int arr[N], n;
inline int tsan(int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>arr[i];
		for(int i=1;i<=n;i++){
			PII ans = {0, i};
			for(int j=1;j<=n;j++){
				if(i==j) continue;
				PII cur = {-tsan(i)-tsan(j), j};
				swap(arr[i], arr[j]);
				cur.FF += tsan(i)+tsan(j);
				ans = min(ans, cur);
				swap(arr[i], arr[j]);
			}
			cout<<ans.SS<<" \n"[i==n];
		}
	}
	return 0;
}

inline int tsan(int x){
	int r=0;
	if(x-1 >= 1) r+=abs(arr[x]-arr[x-1]);
	if(x+1 <= n) r+=abs(arr[x]-arr[x+1]);
	return r;
}