题面 http://codeforces.com/gym/102059/problem/D
题意: 有 3e5 个人排成一列, 然后 Li,Ri 表示每个人可以站在 [Li,Ri] 中的一个, 然后 M(1e6)个限制条件, 某个人一定要在某个人前面, 求一种合法方案, 无解输出 - 1
题解: 首先可以想到对于限制条件, 先进行拓扑排序, 如果不能则无解
针对拓扑排序的结果, 可以更精确每个人站的位置的区间[Li,Ri]
然后从后往前进行考虑, 我们考虑每个位置由谁来坐比较好, 那我们策略是, R 能覆盖这个位置的中, L 最大的那一个来最优,
我们一直维护一个 R 的堆, 每次我们将 R 超过当前位置的人都丢进一个新的堆里, 这个堆按 L 大来排序, 再使用最大的那个 L
如此贪心做完, 不行则无解
- #include<bits/stdc++.h>
- #define lld long long
- #define N 300005
- using namespace std;
- vector<int> g[N];
- int n,m,du[N],x,y,ans[N];
- struct rec
- {
- int l,r,id;
- bool operator <(const rec& a)const
- {
- if (r!=a.r) return r<a.r;
- return l>a.l;
- }
- }a[N];
- struct ssy
- {
- int l,r,id;
- bool operator <(const ssy& a)const
- {
- return l<a.l;
- }
- }b[N];
- int ask()
- {
- priority_queue<ssy>q;
- priority_queue<rec>qq;
- ssy st;
- while (!q.empty()) q.pop();
- while (!qq.empty()) qq.pop();
- for (int i=1;i<=n;i++) if (du[i]==0) qq.push(a[i]);
- for (int i=n;i>=1;i--)
- {
- while (!qq.empty())
- {
- if (qq.top().r<i) break;
- q.push(b[qq.top().id]);
- // cout <<b[qq.top().id].id << endl;
- qq.pop();
- }
- if (q.empty() || q.top().l>i) return 0;
- st=q.top();
- // cout<<st.id << endl;
- q.pop();
- //cout<<"id"<<st.id<<endl;
- ans[i]=st.id;
- for (int j=0;j<g[st.id].size();j++)
- {
- int u=g[st.id][j];
- du[u]--;
- if (du[u]==0) qq.push(a[u]);
- }
- }
- return 1;
- }
- int c[N];
- bool dfs(int u)
- {
- c[u]=-1;
- for (int v=0;v<g[u].size();v++)
- {
- int to=g[u][v];
- if (c[to]<0)
- {
- //cout<<"u xxx:"<<u<<endl;
- //cout<<"1 xxx:"<<to<<endl;
- return 0;
- }else
- if (!c[to] && !dfs(to))
- {
- //cout<<"u xxx:"<<u<<endl;
- //cout<<"1 xxx:"<<to<<endl;
- return 0;
- }
- a[u].l=max(a[u].l,a[to].l+1);
- b[u].l=a[u].l;
- }
- c[u]=1;
- return 1;
- }
- bool toposort()
- {
- memset(c,0,sizeof(c));
- for (int u=1;u<=n;u++) if (!c[u])
- if (!dfs(u)) return 0;
- return 1;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for (int i=1;i<=n;i++)
- {
- scanf("%d%d",&a[i].l,&a[i].r);a[i].id=i;
- b[i].l=a[i].l;
- b[i].r=a[i].r;
- b[i].id=a[i].id;
- }
- for (int i=1;i<=m;i++)
- {
- scanf("%d%d",&x,&y);
- g[y].push_back(x);
- du[x]++;
- }
- if (!toposort()) printf("-1\n");else
- if (!ask()) printf("-1\n");else
- for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
- //for (int i=1;i<=n;i++) cout<<a[i].l<<" "<<a[i].r<<endl;
- }
来源: http://www.bubuko.com/infodetail-2999207.html