PRoblem: 有一个包含n个元素的无序数组，我们要把这个数组变成有序的，但是每次只能交换相邻的两个元素，且对于其中的一个元素来说，每当它被交换一次，它的仇恨值就增加，第一次+1，第二次+2，求怎么排序可以使得所有元素的仇恨值之和最小？返回仇恨值的最小值。 Solution: 1. 交换体现的是相对位置的变换，如果所有元素的相对位置是有序的，那么所有元素一定是有序的，此时问题就转换成了对于每一个元素来说，有多少个元素和它的相对位置不合法？ 2. 我们假设最终有序的数组是从左到右依次增大的，那么按照原数组从左到右的顺序每放一个元素之前，判断一下比他小于等于的元素已经放了多少，设为s，用已经放了的元素数量减去s，得到的就是在原数组中在这个元素左面但是比它大的元素的数量，同理，我们再按照原数组从右到左的顺序每放一个元素之前，判断一下比他小的元素已经放了多少，得到的就是在原数组中在这个元素右面但是比他小的元素的数量，得到不合法的逆序对的数量后，最后求一下和即可。 之前的错误思路：先求出最终有序的数组，然后判断原数组中的元素最终的位置在哪里，然后利用这个差值求和。(错误原因：没有体现交换的思想)
#include<cstdio>#include<iostream>#include<sstream>#include<cstdlib>#include<cmath>#include<cctype>#include<string>#include<cstring>#include<algorithm>#include<stack>#include<queue>#include<set>#include<map>#include<ctime>#include<vector>#include<fstream>#include<list>using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(s) memset(s,0,sizeof(s))const double PI = 3.141592653589;const int INF = 0x3fffffff;const int maxn = 1000000;//左闭右闭struct node{ int l, r, sum; int mid(){ return (l+r)/2; }};node Tree[maxn*4];int value[maxn+10];int flag = 1;//更新值得时候在原值上增加//初始化树，根节点是1void init_tree(int root, int l, int r){ Tree[root].l = l; Tree[root].r = r; if(l == r) Tree[root].sum = value[l]; else{ init_tree(2*root, l, (l+r)/2); init_tree(2*root+1, (l+r)/2 + 1, r); Tree[root].sum = Tree[2*root].sum + Tree[2*root+1].sum; }}//查找和int query_tree(int root, int l, int r){ int m = Tree[root].mid(); if(l == Tree[root].l && r == Tree[root].r) return Tree[root].sum; else{ if(l > m) return query_tree(2*root+1, l, r); else if(r <= m) return query_tree(2*root, l, r); else return query_tree(2*root, l, m) + query_tree(2*root+1, m+1, r); }}void update_tree(int root, int idx, int v){ if(Tree[root].l == Tree[root].r) Tree[root].sum += flag*v; else{ Tree[root].sum += flag*v; if(idx <= Tree[root].mid()) update_tree(2*root, idx, v); else update_tree(2*root+1, idx, v); }}int ans[100010];int num[100010];long long total[100010];int main() {// freopen("/Users/really/Documents/code/input","r",stdin); // freopen("/Users/really/Documents/code/output","w",stdout); ios::sync_with_stdio(false); int n; long long res = 0; cin >> n; for(int i = 1; i <= n; i++) total[i] = total[i-1] + i; init_tree(1, 1, maxn+1); for(int i = 1; i <= n; i++) { cin >> num[i]; update_tree(1, num[i]+1, 1); ans[i] += i - query_tree(1, 1, num[i]+1); } init_tree(1, 1, maxn+1); for(int i = n; i >= 1; i--) { update_tree(1, num[i]+1, 1); if(num[i] != 0) ans[i] += query_tree(1, 1, num[i]); } for(int i = 1; i <= n; i++) { res += total[ans[i]]; } cout << res << endl; return 0;}新闻热点
疑难解答
