「HNOI2005」狡猾的商人

发表于 | 分类于 | | 浏览量： 次

贪心大法好QwQ！

传送门

洛谷P2294

BZOJ1202

题解

这题有好多种解法，可以上差分约束、并查集之类的。

但是贪心大法好啊！！！

把所有偷看到的信息按左端点排序，然后从前到后两两比较。

如果左端点相同

比较右端点

如果右端点相同

比较权值，如果不相同直接输出false

如果右端点不相同

将重叠部分抵消掉，权值相减得到一个新的信息，扔回去，用堆维护

如果左端点不同

把前面一个信息扔掉即可，不用管

直到最后，堆空了，没有出现问题，那么输出true就好了。

代码

其实这题挺水的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int T,n,m;bool fal;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct Node
{
	int L,R,w;
	bool operator < (const Node& b)const{return L<b.L||(L==b.L&&R<b.R);}
	bool operator > (const Node& b)const{return L>b.L||(L==b.L&&R>b.R);}
}tep1,tep2;
priority_queue<Node,vector<Node>,greater<Node> > H;
int main()
{
	T=read();
	while(T--)
	{
		while(H.size()) H.pop();
		n=read();m=read();fal=false;
		for(int i=1;i<=m;i++)
		{
			tep1.L=read();tep1.R=read();tep1.w=read();
			H.push(tep1);
		}
		tep1=H.top();H.pop();
		while(H.size())
		{
			tep2=H.top();H.pop();
			if(tep1.L==tep2.L)
			{
				if(tep1.R==tep2.R)
				{
					if(tep1.w!=tep2.w)
						{printf("false\n");fal=true;break;}
				}
				else if(tep1.R!=tep2.R)
					H.push((Node){tep1.R+1,tep2.R,tep2.w-tep1.w});
			}
			tep1=tep2;
		}
		if(!fal) printf("true\n");
	}
	return 0;
}