解题报告——总共10行代码的神题 CF351E

ywy_c_asm · 2019-05-17 11:55:58 · 个人记录

首先这题的答案是\sum_{i=1}^n\min(\sum_{j<i}[|a_j|<|a_i|],\sum_{j>i}[|a_j|<|a_i|])

我最开始的时候是按取正取负绝对值大小分了16种情况讨论每一对i<j的贡献然后转成一个要建10^7条边的二元关系最小割……，其实……咱们只需要考虑绝对值大小就行了……因为这相当于是重新给他们分配一个正负。

我们暂且不考虑绝对值相等的情况，我们发现当|a_j|<|a_i|的时候a_i的正负才是关键，若a_i取正那么a_j无论正负都小于a_i，那么我们可以对每个a_i分别找出它左右各有多少个绝对值比他小的，就分别是a_i取正取负的代价了，就可以直接取\min加到答案里，因为这仅和a_i有关。

那么绝对值相等的呢？其实结论是在最优情况下所有绝对值相等的取的正负都一样，所以不产生贡献，考虑这个：

____①____A___②___B______③____

假如|A|=|B|，其中①②③分别为这3段里比这个绝对值小的个数，那么就很显然了，因为要取\min，它们绝对不可能往两边取。

（upd：woc好像证伪了……好像不那么显然……

（upd：哦好像知道了，假设1<=2+3,3<=2+1，那么2<=1-3,2<=3-1，除非1=3才行，这样的话还是可以取到同一边。

然后代码真的总共只有10行……

#include<iostream>
#define abs(_o) ((_o<0)?-(_o):(_o))
using namespace std;
int ints[2222];
int main(){
    int n;cin>>n;for(register int i=1;i<=n;i++)cin>>ints[i];int ans=0;for(register int i=1;i<=n;i++){
        int l=0,r=0;for(register int j=1;j<i;j++)if(abs(ints[j])<abs(ints[i]))l++;
        for(register int j=i+1;j<=n;j++)if(abs(ints[j])<abs(ints[i]))r++;ans+=min(l,r);
    }cout<<ans<<endl;return(0);
}