5329. 【NOIP2017提高A组模拟8.22】时间机器

(File IO): input:machine.in output:machine.out
Time Limits: 2000 ms Memory Limits: 262144 KB

Description

Input

Output

Sample Input

3
2 2
1 4 2
3 5 1
1 4 2
2 5 1
3 2
1 3 1
2 4 1
3 5 1
1 3 2
2 5 1
2 2
1 2 2
1 2 1
1 2 1
1 2 2

Sample Output

Yes
No
Yes

Data Constraint

Hint

题解

贪心 将电阻和节点按左端点从小到大排序
按顺序考虑每一种节点
每次贪心选左端点在节点左边，右端点尽量靠近节点的电阻 用set或map维护一下左端点符合条件的右端点即可

代码

#include #include #include #define N 100010 using namespace std; struct point{ long x,y,z,type; }a[N]; map<long,long>b; bool cmp(point a,point b) { if(a.x!=b.x) return a.xelse return a.type>b.type; } int main() { long tot,n,m,i; bool t; freopen("machine.in","r",stdin); freopen("machine.out","w",stdout); scanf("%ld",&tot); while(tot--){ scanf("%ld%ld",&n,&m); for(i=1;i<=n;i++){ scanf("%ld%ld%ld",&a[i].x,&a[i].y,&a[i].z); a[i].type=0; } for(i=1;i<=m;i++){ scanf("%ld%ld%ld",&a[i+n].x,&a[i+n].y,&a[i+n].z); a[i+n].type=1; } sort(a+1,a+n+m+1,cmp); b.clear(); t=true; for(i=1;i<=n+m;i++) if(a[i].type){ if(!b[a[i].y]) b[a[i].y]=a[i].z; else b[a[i].y]+=a[i].z; }else{ while(a[i].z){ map<long,long>::iterator iter=b.lower_bound(a[i].y); if(iter==b.end()){ t=false; break; } if(a[i].zsecond){ iter->second-=a[i].z; a[i].z=0; }else{ a[i].z-=iter->second; b.erase(iter); } } if(!t)break; } if(t) printf("Yes "); else printf("No "); } return 0; }