C. Vasya And Array
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int t[1005],l[1005],r[1005],rest;
int cf[1005],sum[1005],tot=1,dx[1005],res[1005];
int main(){ cin>>n>>m;rest=n; for(int i=1;i<=m;i++){ cin>>t[i]>>l[i]>>r[i]; if(t[i]==1){ cf[l[i]]++; cf[r[i]]--; } } int sum=0; for(int i=1;i<=n;i++){ sum+=cf[i]; if(sum>0){ dx[i]=0; } else dx[i]=-1; } res[0]=n; for(int i=1;i<=n;i++){ res[i]=res[i-1]+dx[i]; } for(int i=1;i<=m;i++){ if(t[i]==0){ if(res[l[i]-1]-res[r[i]-1]==0){ cout<<"NO"<<endl; return 0; } } } cout<<"YES"<<endl; for(int i=0;i<n;i++){ cout<<res[i]<<" "; }
}
嘛，我看到这个题，原本是想乱搞，没有想到差分。。。。
。。。。。
首先差分------让每一个区间+1
随后再前缀和， 每个位置为0的就说明这个位置不是排序的
随后关键的一个暴力
1：前缀和搞一搞
因为题目要求t1区间内严格不下降 那直接严格的相等（最好相等于N<----->考虑到就算没有t1的情况也可以下降n次，保证最后有的分配）
令num=n
然后对于每个位置大于0的就是num，遇到等于0就num-1，然后接着来，，，最后处理处P（保证了答案的正确性的同事，也体现了暴力之美。。。。。）
然后就是判断YES,NO
当Ti为0时，如果Li位置上的前缀和小于等于Ri位置上的前缀和，那就肯定是NO
因为当Li==Ri时，这个区间相等，不满足unsort
综上
Q.E.D
哔哩哔哩公司氛围 95人发布
投递海康威视等公司10个岗位