题意
最后要形成形如前面从1k范围内全为负数,从k+1n范围内全为正数,没有0的存在,
那此时最少应该改变几个值。
解析
ca[i]统计前面到i一共有多少个>=0的,cb[i]代表后面到i一共有多少个<=0的
划分分界点k,求最小的ca[k] + cb[k+1]。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10,M = 1e6 + 10;
int n;
int a[N],ca[N],cb[N];
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
ca[i] = ca[i-1] + (a[i] >= 0);
}
for(int i=n;i;i--){
cb[i] = cb[i+1] + (a[i] <= 0);
}
int res = 1 << 30;
for(int i=1;i<n;i++){
res = min(res,ca[i] + cb[i+1]);
}
printf("%d",res);
return 0;
}
标签:1300,int,cb,ca,long,txt,CF234C
From: https://www.cnblogs.com/dtdbm/p/17009283.html