CF1437E Make It Increasing
给你一个数列 a ,一个集合 b , 对于每个 b 中的元素x, a_x 不能修改,其他都可以修改,问最少多少次可以将 a 修改为严格单调递增的。如果不存在,输出 -1 。
a 中的所有元素在任意时刻必须都是整数。
首先先判断是否合法,要保证两个不能改变的数a_{b_i}和a_{b_{i+1}}之间够不够放下b_{i+1}-b_i个数
if(a[b[i+1]]-a[b[i]]<b[i+1]-b[i])
puts("-1");//放不下
然后考虑,如果要让序列递增,那么必有
a_{i+1}-a_i\geq 1
即
a_{i+1}-a_i\geq i+1-i
那么就是
a_{i+1}-(i+1)\geq a_i-i
那么我们令c_i=a_i-i,我们想使修改的数的尽量少,就要在原序列找到一个**包含所有不可修改的数 **(a_{b_i})的最长不下降子序列。
由于这个限制条件,必须在 nlogn 求 LIS 的方法下作出修改。
for(int i=1;i<=n;++i){
if(!top||a[i]>=q[top]){
q[++top]=a[i];
if(i==b[t]){
++t;
lb=top;
}
}
else{
int p=std::upper_bound(q+1,q+1+top,a[i])-q;
if(p<=lb)
continue;
q[p]=a[i];
if(b[t]==i){
++t;
lb=p;
top=p;
}
}
}
记录前一个必须包含的数的坐标为 lb ,如果当前的数a_i当前的可以接在子序列后,就直接接,如果受到限制,就记录。
如果不可以接,考虑更新最长子序列的数组。
在原数组中找到比a_i大的第一个数,记录下标为p
如果 p 在 lb 前面,由于a_{lb}>a_i,所以当前数不可更新子序列q数组。
然后可以考虑更新子序列q数组
如果当前的数是受限制的,那么子序列从当前数字后的数必须全部舍去(因为这个数必须加入子序列数组,如果不舍去,子序列就不是不下降的了)此时p成为了子序列数组的最后一个数。
#include<bits/stdc++.h>
const int N = 5e5+10;
int a[N],b[N],t=1,q[N],top=0;
int n,m,lb;
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=m;++i){
scanf("%d",&b[i]);
}
std::sort(b+1,b+1+m);
for(int i=1;i<=m-1;++i){
if(a[b[i+1]]-a[b[i]]<b[i+1]-b[i]){
puts("-1");
return 0;
}
}
for(int i=1;i<=n;++i)
a[i]-=i;
for(int i=1;i<=n;++i){
if(!top||a[i]>=q[top]){
q[++top]=a[i];
if(i==b[t]){
++t;
lb=top;
}
}
else{
int p=std::upper_bound(q+1,q+1+top,a[i])-q;
if(p<=lb)
continue;
q[p]=a[i];
if(b[t]==i){
++t;
lb=p;
top=p;
}
}
}
printf("%d",n-top);
return 0;
}
0 条评论