首页 > 代码库 > Codeforces 556D - Case of Fugitive
Codeforces 556D - Case of Fugitive
556D - Case of Fugitive
思路:将桥长度放进二叉搜索树中(multiset),相邻两岛距离按上限排序,然后二分查找桥长度匹配并删除。
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e5+5; struct node { ll x; ll y; int id; bool operator <(const node &a)const { return y<a.y; } }l[N],b[N]; struct Node { ll x; int id; bool operator <(const Node &a)const { return x<a.x; } }a[N]; int ans[N]; multiset<Node>ss; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; cin>>b[0].x>>b[0].y; for(int i=1;i<n;i++) { cin>>b[i].x>>b[i].y; l[i-1].x=b[i].x-b[i-1].y; l[i-1].y=b[i].y-b[i-1].x; l[i-1].id=i; } for(int i=0;i<m;i++) { cin>>a[i].x; a[i].id=i+1; ss.insert(a[i]); } sort(l,l+n-1); for(int i=0;i<n-1;i++) { auto it=ss.lower_bound(Node{l[i].x,0}); if(it==ss.end()) { cout<<"No"<<endl; return 0; } if(it->x<=l[i].y) { ans[l[i].id]=it->id; ss.erase(it); } else { cout<<"No"<<endl; return 0; } } cout<<"Yes"<<endl; for(int i=1;i<n-1;i++) cout<<ans[i]<<" "; cout<<ans[n-1]<<endl; return 0; }
Codeforces 556D - Case of Fugitive
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。