改变数组元素
题目 改变数组元素
思路分析
每进行一次操作 就让最后i个数变成1
直接想到差分
注意几个边界问题
不难得知这个区间就是i-a[i]+1处++ i处--
但如果i-a[i]+1<0呢 那就越界了
这个情况实际是把所有数都置成1(区间变成1 ，i）
所以可以用max(1,i-a[i]+1）确定左区间
然后一个性质就是 和之前有道题“合格数”差不多 它也不在乎数组里具体是什么
有就是1 没有就是0
感觉这也是差分和区间合并的一个交集的地方 好像有这种性质的大都能用区间合并写
那么来看第二种 区间合并的写法
把每次的操作读入 不急着做 因为它每次都是把一些置1 这就有很多重复的地方
我完全可以把能合并的操作都合并起来
再统一做置1的操作
这个过程可以朴素的直接把st~ed的数置1
也可以再结合差分
在区间开始处+1 结尾处-1
然后发现还没有直接差分快hhh
代码实现
差分 531ms
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N];
int T,n;
int main()
{
cin>>T;
while(T--){
cin>>n;
memset(b,0,(n+1)*4);// 重置差分数组 其实只要前(n+1)个数
for(int i=1;i<=n;i++){
cin>>a[i];//也可以不用开a[]存 直接用x读入就行
//让前i个数变成1 找到左右区间准备做差分
//如果左边越界就直接从第一个数开始全设为1
int l=max(1,i-a[i]+1),r=i;
b[l]++,b[r+1]--;
}
//构造前缀和 但不在于具体是几 有就是1 没有就是0
for(int i=1;i<=n;i++){
b[i]+=b[i-1];
if(b[i])
cout<<1<<" ";
else
cout<<0<<" ";
}
cout<<endl;
}
return 0;
}
区间合并873ms
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;
vector<PII> ranges;
int ans[N];
int T,n;
int main()
{
cin>>T;
while(T--){
cin>>n;
memset(ans,0,(n+1)*4);// 重置前(n+1)个数
ranges.clear();
for(int i=1;i<=n;i++){
int x;
cin>>x;
//这里要特判一下 是0才加入
//直接差分就不需要 因为l=i+1 r=i 右边又是r+1 所以抵消
if(x>0){
int l=max(1,i-x+1),r=i;
ranges.push_back({l,r});
}
}
sort(ranges.begin(),ranges.end());
int st=-1,ed=-1;
for(auto range:ranges){
if(ed+1<range.first){//1~2 3~4这种也能合并
if(ed!=-1)
for(int i=st;i<=ed;i++)
ans[i]=1;
st=range.first,ed=range.second;
}
else if(ed<range.second)
ed=range.second;
}
if(ed!=-1)
for(int i=st;i<=ed;i++)
ans[i]=1;
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
return 0;
}
区间合并加差分 832ms
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;
vector<PII> ranges;
int ans[N];
int T,n;
int main()
{
cin>>T;
while(T--){
cin>>n;
memset(ans,0,(n+1)*4);// 重置前(n+1)个数
ranges.clear();
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x>0){
int l=max(1,i-x+1),r=i;
ranges.push_back({l,r});
}
}
sort(ranges.begin(),ranges.end());
int st=-1,ed=-1;
for(auto range:ranges){
if(ed+1<range.first){
if(ed!=-1){
ans[st]++;//把全赋1改成差分形式的++--
ans[ed+1]--;
}
st=range.first,ed=range.second;
}
else if(ed<range.second)
ed=range.second;
}
if(ed!=-1){
ans[st]++;//同理
ans[ed+1]--;
}
for(int i=1;i<=n;i++){
ans[i]+=ans[i-1];
cout<<ans[i]<<" ";
}
cout<<endl;
}
return 0;
}
💬 评论