首页 > 其他 > 详细

#前缀和,后缀和#洛谷 4280 [AHOI2008]逆序对

时间:2020-02-24 01:16:13      阅读:88      评论:0      收藏:0      [点我收藏+]

题目传送门


分析

首先填的数字单调不降,感性理解
那可以维护\([a_1\sim a_{i-1}]\)\(cnt\)后缀和以及
\([a_{i+1}\sim a_n]\)\(cnt\)前缀和,那可以\(O(k)\)判断怎样选最小
然后\(a_i=-1\)的答案就能找出来,然后用这些修改后缀和,时间复杂度\(O(nk)\)


代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
int n,a[10011],pre[111],ans,suf[111],m;
inline signed iut(){
    rr int ans=0,f=1; rr char c=getchar();
    while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans*f;
}
signed main(){
    n=iut(); m=iut();
    for (rr int i=1;i<=n;++i){
        a[i]=iut();
        if (a[i]!=-1) ++pre[a[i]];
    }
    for (rr int i=2;i<=m;++i) pre[i]+=pre[i-1];
    for (rr int i=1;i<=n;++i){
        if (a[i]==-1){
            rr int pos=0,mn=1e9;
            for (rr int j=1;j<=m;++j)
            if (suf[j+1]+pre[j-1]<mn)
                mn=suf[j+1]+pre[j-1],pos=j;
            a[i]=pos;
        }else for (rr int j=a[i];j<=m;++j) --pre[j];
        ans+=suf[a[i]+1]; for (rr int j=1;j<=a[i];++j) ++suf[j];
    }
    return !printf("%d",ans);
}

#前缀和,后缀和#洛谷 4280 [AHOI2008]逆序对

原文:https://www.cnblogs.com/Spare-No-Effort/p/12355204.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!