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<cstdio>
#include<algorithm>
#include<map>
#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.x<b.x;
else
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].z<iter->second){
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\n");
else
printf("No\n");
}
return 0;
}