紫书习题 8-23 UVa 1623 （set妙用 + 贪心）

这道题我是从样例中看出思路了

2 4

0 0 1 1

看这组数据，输出的是No，为什么呢？因为两个1之间没有神龙喝水，所以一定会有水灾。

然后就启发了我，两次同一个湖的降水之间必须至少有一次神龙喝水，否则就会有水灾。

如果是第一个湖的话那么就看作在第0次有一次降水。

所以每一次找就用二分来找离前一次降水最近的那一次来喝水。

然后我思路是对的，但是实现的时候想复杂了很多。

因为这个思路涉及不断地修改一个有序的数列，我就想用vector，然后用过就标记，下一次找的时候用

一个while循环来略去标记过的。事实证明很复杂，很容易写错。

然后看到博客，看到用一个set来实现，非常的简洁方便，核心代码非常的短。

因为set本身就是有序的，同时自带二分，而且删除很方便。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<set>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 1123456;

int ans[MAXN], pre[MAXN], rain[MAXN];

int main()

{

	int T, n, m;

	scanf("%d", &T);

	while(T--)

	{

		memset(pre, 0, sizeof(pre));

		memset(ans, 0, sizeof(ans));

		set<int> s;

		scanf("%d%d", &n, &m);

		REP(i, 0, m) scanf("%d", &rain[i]);

		bool ok = true;

		REP(i, 0, m)

		{

			if(rain[i] == 0)

			{

				s.insert(i);

				continue;

			}			

			ans[i] = -1;

			auto it = s.lower_bound(pre[rain[i]]);

			if(it == s.end()) { ok = false; break; }

			ans[*it] = rain[i];

			pre[rain[i]] = i;

			s.erase(*it);

		}

		if(!ok) puts("NO");

		else

		{

			puts("YES");

			bool first = true;

			REP(i, 0, m)

				if(ans[i] != -1)

				{

					if(first) first = false;

					else printf(" ");

					printf("%d", ans[i]);

				}

			puts("");

		}

	} 

	return 0;

}

巴特西

紫书习题 8-23 UVa 1623 （set妙用 + 贪心）

最新文章

热门文章

巴特西

紫书 习题 8-23 UVa 1623 （set妙用 + 贪心）

最新文章

热门文章

紫书习题 8-23 UVa 1623 （set妙用 + 贪心）