【NOIP 2013 DAY.1】火柴排队【codevs 3286】
分析:贪心策略。第一行第一小对第二行第一小、第一行第二小对第二行第二小。。。类推。
即:排序,求排序的次数。
(归并排序求逆序对)【记录交换的次数即是答案】*推荐使用归并。本题最优解法。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=99999997;
int a[100005],b[100005];
int l[100005],r[100005];
int s[100005],t[100005];
int rr[100005];
int sum;
int n;
void m_sort(int x,int y)
{
if(y-x>1)
{
int m=x+(y-x>>1);
int p=x,q=m,i=x;
m_sort(x,m);
m_sort(m,y);
while(p<m || q<y)
{
if(q>=y || (p<m && s[p]<=s[q])) t[i++]=s[p++];
else
{
t[i++]=s[q++];
sum+=m-p;
}
}
for(i=x;i<y;i++) s[i]=t[i];
}
sum%=mod;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d"