CodeForces - 556D Case of Fugitive
题目链接
https://codeforces.com/problemset/problem/556/D
解题思路
贪心+点匹配区间问题
点匹配区间问题例题及讲解
不想多说了,感觉挺板子的。
特别注意输出是“Yes”/“No”,而不是“YES”/“NO”!!!
AC代码
#include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const int N=2e5+5; typedef pair<ll,int> pli; priority_queue<pli,vector<pli>,greater<pli> > q; int n,m,ans,cnt=1,res[N]; ll r[N],l[N]; struct node { ll l,r; int idx; }a[N],b[N]; bool cmp(node c,node d) { return c.l<d.l; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>l[i]>>r[i]; if(i==1) continue; a[i-1].l=l[i]-r[i-1]; a[i-1].r=r[i]-l[i-1]; a[i-1].idx=i-1; } for(int i=1;i<=m;i++) cin>>b[i].l,b[i].idx=i; n--; sort(a+1,a+n+1,cmp); sort(b+1,b+m+1,cmp); for(int i=1;i<=m;i++) { while(cnt<=n && a[cnt].l<=b[i].l) q.push(pli(a[cnt].r,cnt)),++cnt; while(!q.empty()) { ll tmp=q.top().fi;int id=q.top().se;q.pop(); if(tmp>=b[i].l) { ++ans,res[a[id].idx]=b[i].idx; break; } } } if(ans>=n) { puts("Yes"); for(int i=1;i<=n;i++) cout<<res[i]<<(i==n?'\n':' '); } else puts("No"); }
思维 文章被收录于专栏
思维题都会了,ACM金牌就稳了! 我骗你的!