CF351E Jeff and Permutation

Description

https://www.luogu.com.cn/problem/CF351E

Solution

2200 不会做，警戒。

观察到读入进来的数的正负没有关系，所以先把他全部取绝对值。

如果 $a_i<a_j$，则无论怎么改变 $a_i$ 的正负对答案无影响。影响答案的是 $a_j$ 的正负。这样每个 $a_j$ 独立。

只需要对讨论 $a_j$ 的正负分别对答案的影响，取 $\min$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n,a[maxn],l,r,ans;
signed main(void){
//	freopen("1.in","r",stdin);
	int i,j;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),a[i]=abs(a[i]);
	for (i=1;i<=n;i++) {
		l=r=0;
		for (j=1;j<=n;j++) if (i^j) {
			if (a[j]<a[i]) {
				if (j<i) l++;
				else r++;
			}
		}
		ans+=min(l,r);
	}
	printf("%d",ans);
	return 0;
}