标签：Tasks 扩增 int max 100005 fail
- 【构造思路】有序化问题，按b从大到小考虑，构造当前的合法方案中包容性最强的方案，动态判断
- 首先，对于最大的b，让r=l就好了，需不需要让r稍大一点，来让它避免被其他区间覆盖？不可能有这种情况
- 其次，对于所有的b-1，你需要为所有的b都找到一个覆盖它的区间，并且所有的b-1之间都不会相互覆盖
- 以此类推，构造下去就好了
- 对于禁止区间全等的限制：我们有两种选择，一种是选择更小的l,一种是将r扩增1；我们希望在最后的方案中，最大的r最小
- 其实我觉得应该优先选择更小的l，如果不行再扩增r,但是直接扩增r也能过，想不明白就不想了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>p[100005];
int l[100005],r[100005];
void fail()
{
cout<<-1<<endl;
exit(0);
}
bool cmp(int a,int b)
{
return l[a]<l[b];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m=0;
cin>>n;
for(int i=1;i<=n;i++)
{
int b;
cin>>l[i]>>b;
m=max(m,b);
p[b].push_back(i);
}
for(int i=0;i<=m;i++)
{
if(p[i].empty())
{
fail();
}
sort(p[i].begin(),p[i].end(),cmp);
for(int j=1;j<p[i].size();j++)
{
if(l[p[i][j]]==l[p[i][j-1]])
{
fail();
}
}
}
for(int i=1;i<=n;i++)
{
r[i]=l[i];
}
for(int i=m-1;i>=0;i--)
{
for(int j=0;j<p[i+1].size();j++)
{
int k=-1;
while(k+1<p[i].size()&&l[p[i][k+1]]<=l[p[i+1][j]])
{
k++;
}
if(k==-1)
{
fail();
}
if(l[p[i][k]]!=l[p[i+1][j]])
{
r[p[i][k]]=max(r[p[i][k]],r[p[i+1][j]]);
}
else
{
if(k>0)
{
k--;
r[p[i][k]]=max(r[p[i][k]],r[p[i+1][j]]);
}
else
{
r[p[i][k]]=max(r[p[i][k]],r[p[i+1][j]]+1);
}
}
}
for(int j=1;j<p[i].size();j++)
{
r[p[i][j]]=max(r[p[i][j]],r[p[i][j-1]]+1);
}
}
for(int i=1;i<=n;i++)
{
if(r[i]>1000000)
{
fail();
}
}
for(int i=1;i<=n;i++)
{
cout<<r[i]<<"\n";
}
return 0;
}
标签：Tasks,
扩增,
int,
max,
100005,
fail
From： https://www.cnblogs.com/watersail/p/18413747