bzoj 1786 [Ahoi2008]Pair 配对

 

转载请注明出处：

http://www.cnblogs.com/hzoi-wangxh/p/7738619.html

1786: [Ahoi2008]Pair 配对

Time Limit: 10 Sec   Memory Limit: 64 MB
Submit: 857   Solved: 559

Description

Input

Output

Sample Input

5 4
4 2 -1 -1 3

Sample Output

4

题解：

感觉像是一个贪心吧……反正能过。

我们就是由前向后枚举-1的位置，之后寻找它是几时它所贡献的逆序对最少，如果有相同的，取较小的数。因为k<=100，所以我们直接枚举到k即可。求逆序对时用树状数组维护，前面的建一个，后面的建一个。

感性证明：从前向后找，要使后面的数尽量大，前面的数尽量小，才能使逆序对最少。每次枚举-1所代表的数，只要让它的逆序对最少并且对后面可能的贡献尽量小即可。后面的一般会比前面求得的数大。

不管怎么说，反正能过。

附上代码：

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[10010],n,sum,k,s1[110],s2[110],ans;
void add2(int,int);
void add1(int,int);
int query1(int);
int query2(int);
int work();
int lowbit(int x)
{return x&(-x);
}
int main()
{
//  freopen("in.txt","r",stdin);scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]!=-1){add2(a[i],1);ans+=query2(k)-query2(a[i]);}}for(int i=1;i<=n;i++){if(a[i]>0) add2(a[i],-1),add1(a[i],1);else a[i]=work();}printf("%d",ans);return 0;
}
void add2(int x,int y)
{while(x<=k){s2[x]+=y;x+=lowbit(x);}
}
void add1(int x,int y)
{while(x<=k){s1[x]+=y;x+=lowbit(x);}
}
int query1(int x)
{int sum=0;for(int i=x;i>=1;i-=lowbit(i))sum+=s1[i];return sum;
}
int query2(int x)
{int sum=0;for(int i=x;i>=1;i-=lowbit(i))sum+=s2[i];return sum;
}
int work()
{int le=1,ri=k;int z=0,mmax=0x7fffffff;for(int i=1;i<=k;i++){int l=query2(i-1)+query1(k)-query1(i);if(l<mmax){mmax=l;z=i;}}ans+=query2(z-1)+query1(k)-query1(z);add1(z,1);return z;
}