做捐款网站,网站动态设计效果,山东兴润建设集团网站,贵阳网站建设公司哪个好文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴一维差分区间合并一、题目
1、原题链接 3729. 改变数组元素 2、题目描述 给定一个空数组 V 和一个整数数组 a1,a2,…,an。 现在要对数组 V 进行 n 次操作。 第 i 次操作的…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴一维差分区间合并一、题目
1、原题链接 3729. 改变数组元素 2、题目描述 给定一个空数组 V 和一个整数数组 a1,a2,…,an。 现在要对数组 V 进行 n 次操作。 第 i 次操作的具体流程如下 从数组 V 尾部插入整数 0。 将位于数组 V 末尾的ai个元素都变为 1已经是 1 的不予理会。 注意 ai 可能为 0即不做任何改变。ai 可能大于目前数组 V 所包含的元素个数此时视为将数组内所有元素变为 1。 请你输出所有操作完成后的数组 V。 输入格式 第一行包含整数 T表示共有 T 组测试数据。 每组数据第一行包含整数 n。 第二行包含 n 个整数 a1,a2,…,an。 输出格式 每组数据输出一行结果表示所有操作完成后的数组 V数组内元素之间用空格隔开。 数据范围 1≤T≤20000,1≤n≤2×105,0≤ai≤n,保证一个测试点内所有 n 的和不超过 2×105。 输入样例 3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0输出样例 1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0二、解题报告
1、思路分析
思路1差分区间合并 1将每个需要1的区间合并得到若干个不重叠的区间。 2对每个区间利用差分将每个区间元素值1。 3对差分数组求前缀和得到结果数组输出即可。 思路2y总思路 思路来源y总每日一题b站视频链接 y总yyds 1直接对每个区间进行差分将每个区间元素值1。 2对差分数组求前缀和得到数组如果数组元素值1说明进行了1操作直接输出1否则说明该值没有1直接输出0。
2、时间复杂度
思路1时间复杂度O(nlogn)sort()函数、快排时间复杂度nlogn级别 思路2时间复杂度O(n)
3、代码详解
思路1代码
#include iostream
#include algorithm
#include utility
#include vector
#include cstring
using namespace std;
typedef pairint,int PII;
vectorPII v;
const int N200010;
int pos;
int t,n;
int a[N],b[N];
//区间合并
void merge(vectorPII vec){vectorPII ans;sort(vec.begin(),vec.end());int st-1,ed-1;for(auto i:vec){if(edi.first){if(st!-1) ans.push_back({st,ed});sti.first,edi.second;}else edmax(ed,i.second); }if(st!-1) ans.push_back({st,ed});vecans;
}
//差分
void insert(int l,int r,int c){b[l]c;b[r1]-c;
}
int main(){cint;while(t--){cinn;for(int i1;in;i){posi; //pos记录当前数组中元素的个数cina[i];if(a[i]0) continue; //如果需要将0个元素置为1跳过下面步骤执行下一次循环if(posa[i]){ //如果需要置为1的元素个数超过数组元素个数v.push_back({1,pos}); //需置成1的区间为整个数组}else{v.push_back({pos-a[i]1,pos}); //否则需置成1的区间为数组后a[i]个元素所在区间}}merge(v);for(auto i:v){insert(i.first,i.second,1);}//差分数组求前缀和得到结果数组for(int i1;ipos;i){b[i]b[i-1];coutb[i] ;}coutendl;memset(b,0,sizeof b); //注意不要忘记下一次循环前需将元素置为0pos0; //pos也别忘记v.clear(); //区间数组也得清空} return 0;
}思路2代码
#include iostream
#include algorithm
#include cstring
using namespace std;
const int N200010;
int t,n;
int a[N],b[N];
//差分
void insert(int l,int r,int c){b[l]c;b[r1]-c;
}
int main(){cint;int pos0;while(t--){cinn;for(int i1;in;i){posi; //pos代表当前元素个数cina[i];if(a[i]0) continue; //如果需要把0个元素置为1直接跳过下面步骤执行下一次循环if(a[i]pos){ //如果需要置的元素个数大于等于区间元素数insert(1,pos,1); //将[1,pos]即整个区间加1}else{insert(pos-a[i]1,pos,1); //否则只个数组后a[i]个元素加1}}//差分数组求前缀和得到每个区间加1后的结果数组for(int i1;ipos;i){b[i]b[i-1];if(b[i]1) cout1 ; //如果某个位置加了大于等于1次个1输出1else cout0 ; //如果没有加过1输出0}coutendl;memset(b,0,sizeof b); //注意不要忘记下一次循环前需将元素置为0pos0; //pos也别忘记}return 0;
}三、知识风暴 一维差分 一维差分可以快速地给指定区间的每个数加任意常数c差分数组顾名思义就是相邻元素之差组成的数组。我们如果要对某个区间加减任意常数c可以先求其差分数组然后对差分数组进行操作。设b数组为差分数组。 操作对[l,r]区间每个数cb[l]c,b[r1]-c。 最后再对差分数组求前缀和即为处理后的原数组。 区间合并 区间合并就是将某些有重叠或者说是相交的区间合并。基本思路 将所有需要合并的区间按左端点排好序。以排好序的第一个区间开始看第二个区间是否与第一个区间有重叠而且右端点比第一个区间大如果满足则合并合并操作就是将第一个区间的右端点更新成第二个区间的右端点如果第二个区间被第一个区间所完全覆盖则合并后的区间就是第一个区间不需要操作如果第二个区间和第一个区间完全没有交集说明第二个区间的左端点比第一个区间的右端点大而我们又是按照区间左端点进行排序的则下一个区间的左端点也比第一个区间的左端点大说明当前第一个区间已经和后面所有区间都不可能有交集了所以第一个区间已经合并完成我们将其放入结果数组中下一次将剩下区间里的第一个区间进行如上合并操作直到完成所有区间合并操作将最后一个区间也放入结果数组合并完成。
