CF761D Dasha and Very Difficult Problem（构造 思维）

​​linkkk​​ 题意：

现有a[i]，b[i]两个数组(l<=a[i]<=b[i]<=r),我们定义p,c两个数组,其中c[i]=b[i]-a[i],p数组是c数组的相对大小,现给你a和p数组,把任意满足的一组b数组求出来.如果没有满足的,则输出‘-1’(没有引号)

思路：
先按照从小到大排序，然后贪心的去构造，尽可能的让小，并且还要满足
代码：

// Problem: D. Dasha and Very Difficult Problem
// Contest: Codeforces - Codeforces Round #394 (Div. 2)
// URL: https://codeforces.com/problemset/problem/761/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=2e5+100;

int n,l,r,ans[maxn],id[maxn];

struct node{
int a,p;
}a[maxn];

bool cmp(node a,node b){
return a.p<b.p;
}

int main(){
cin>>n>>l>>r;
for(int i=1;i<=n;i++) cin>>a[i].a;
for(int i=1;i<=n;i++) cin>>a[i].p,id[a[i].p]=i;
sort(a+1,a+1+n,cmp);
ans[id[a[1].p]]=l;
int las=l-a[1].a+1;
for(int i=2;i<=n;i++){
ans[id[a[i].p]]=max(l,las+a[i].a);
if(ans[id[a[i].p]]>r){
puts("-1");return 0;
}
las=max(las,ans[id[a[i].p]]-a[i].a)+1;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";

return 0;
}

【文章转自香港云服务器 http://www.1234xp.com 复制请保留原URL】