承德网站开发公司,成都制作网站价格表,wordpress电子商务,易名中国域名门户网站题意
给我们一个序列 序列长度小于500000 每个元素 小于999999999 让我们只移动相邻的元素 最终使得他们移动到正好上升序的最小移动次数
分析
我们看 最小的移动次数其实是个幌子 因为你移动相邻的元素 大的元素你不论如何移动 就是要一个个移动到所有比他小的元素的后面…题意
给我们一个序列 序列长度小于500000 每个元素 小于999999999 让我们只移动相邻的元素 最终使得他们移动到正好上升序的最小移动次数
分析
我们看 最小的移动次数其实是个幌子 因为你移动相邻的元素 大的元素你不论如何移动 就是要一个个移动到所有比他小的元素的后面 来看原序列 9 1 0 5 4 对于9由于它是最大的 那么他就要慢慢移动到最后一个 变成 1 0 5 4 9 那么此时可以忽略9 只看前面的元素 因为9已经归位 1 0 5 4 中 5 最大 那么换到最后 变成 1 0 4 5 有效序列变成 1 0 4 注意 我们在换的过程中 有没有保证满足最小交换次数 我们移动9 的时候 无论怎么移动 都要保证9 最后在最后一个位置上 那么无论移动后面的元素 还是移动9 都是要么把后面的元素移动到前面来 要么把9移动到后面去 其实移动9还是移动后面元素 其实都可以看成一个方向改变序列 那么在只交换相邻元素位置下的情况 其实没有最小 我们求出来交换次数 就是最小 因为他不可能跨元素移动 那么就是变成求逆序数问题了 每个元素前有几个逆序 就要移动几次 当然要离散化啦!
code
#includeiostream
#includealgorithm
#includecstdio
#includecstring
using namespace std;
typedef long long ll;
const int lim 500010;
int c[lim],a[lim];
struct node{int x,id;// value and th
}t[lim];
void add(int x,int val){while(xlim){c[x]val;xx(-x);}
}
ll sum(int x){ll ans 0;while(x){ansc[x];x-x(-x); } return ans;
}
bool cmp(node a,node b){return a.xb.x;
}
int main()
{int n;while(scanf(%d,n),n){for(int i1;in;i)scanf(%d,t[i].x),t[i].id i;sort(t1,t1n,cmp);for(int i1;in;i)a[t[i].id] i;ll s0;for(int i1;in;i){add(a[i],1);smax(i-sum(a[i]),1ll*0);//couti-sum(a[i])endl; } printf(%lld\n,s); memset(c,0,sizeof(c)); }return 0;
}如果数据中有重复元素 还可以这样离散化 int ans unique(t1,t1n)-t-1; // 去重sort(t1,t1ans); // 排序 for(int i1;in;i) //找排名a[i] lower_bound(t1,t1ans,a[i])-t;
