首页 > 代码库 > CF 496E Distributing Parts
CF 496E Distributing Parts
通过这题我才知道lower_bound(set)，和set::lower_bound完全他妈不一样。。前者O（n）后者O（logn），去他妈的。。。。
思路：
另要被覆盖的线段为a[i]，覆盖它的先端为b[i]
对要被覆盖的线段的左端点及a[i].lef进行离散化，然后从小到大扫描过去，如果b[i].lef<=扫描线的值就把<b[i].rig,i>加入set，如果b[i].rig<扫描线的值就从set里面删除<b[i].rig,i>，然后就处理询问了,从set里面找到离a[i].rig最近的即可。
#include <cstdio>#include <cstring>#include <set>#include <algorithm>using namespace std;#define N 100000struct Node{ int lef,rig,val,laber;} a[N+20],b[N+20];int c[N+20],ans[N+20];bool vist[N+20];set<pair<int,int> > heap;bool cmp1(const Node &x,const Node &y){ return x.lef<y.lef||(x.lef==y.lef&&x.rig<y.rig);}int main(){ //freopen("input","r",stdin); int n; scanf("%d",&n); int cnt = 0; for (int i=0; i<n; i++) { scanf("%d%d",&a[i].lef,&a[i].rig); a[i].laber = i; c[cnt++] = a[i].lef; } int m; scanf("%d",&m); for (int i=0; i<m; i++) { scanf("%d%d%d",&b[i].lef,&b[i].rig,&b[i].val); b[i].laber = i; } sort(a,a+n,cmp1); sort(b,b+m,cmp1); sort(c,c+n); int len = unique(c,c+n) - c; int bl = 0, br = 0; int k = 0; for (int i=0; i<len&&k<n; i++) { while (b[bl].lef<=c[i]&&bl<m) { heap.insert(pair<int,int>(b[bl].rig,bl)); bl++; } while (b[br].rig<c[i]&&br<m) { if (!vist[br]) heap.erase(pair<int,int>(b[br].rig,br)); br++; } while (a[k].lef==c[i]&&k<n) { if (heap.empty()) { printf("NO\n"); return 0; } set<pair<int,int> >::iterator it = heap.lower_bound(pair<int,int>(a[k].rig,-1)); if (it==heap.end()) { printf("NO\n"); return 0; } pair<int,int> j = *it; ans[a[k].laber] = b[j.second].laber; b[j.second].val--; //printf("%d %d\n",j.second,b[j.second].val); if (b[j.second].val==0) { heap.erase(it); vist[j.second] = true; } k++; } } printf("YES\n"); for (int i=0; i<n; i++) printf("%d ",ans[i]+1); printf("\n"); return 0;}
CF 496E Distributing Parts
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。