首页 > 代码库 > UVa1623 Enter The Dragon (贪心)
UVa1623 Enter The Dragon (贪心)
链接:http://bak2.vjudge.net/problem/UVA-1623
分析:用集合st保存当前还可以让神龙喝干湖水的日子,数组full[i]保存i号湖上次满水的日子。每当到了要往湖里下雨的日子,在集合st里查找这个湖最后一次满水的日子后第一个没被用掉不下雨的日子去喝干这个湖水,维护这个湖最后一次满水的日子,把用掉的日子从集合st里删除。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <set> 5 using namespace std; 6 7 const int maxn = 1000000 + 5; 8 9 int n, m, full[maxn], ans[maxn];10 set<int> st;11 12 int main() {13 int T;14 scanf("%d", &T);15 while (T--) {16 scanf("%d%d", &n, &m);17 memset(full, 0, sizeof(full));18 memset(ans, 0, sizeof(ans));19 st.clear();20 bool ok = true;21 for (int i = 1; i <= m; i++) {22 int t; scanf("%d", &t);23 if (!ok) continue;24 if (!t) st.insert(i);25 else {26 ans[i] = -1;27 set<int>::iterator it = st.upper_bound(full[t]);28 if (it == st.end()) ok = false;29 else {30 ans[*it] = t;31 full[t] = i;32 st.erase(*it);33 }34 }35 }36 if (!ok) printf("NO\n");37 else {38 printf("YES");39 bool first = true;40 for (int i = 1; i <= m; i++)41 if (ans[i] >= 0) printf("%c%d", first?(first = false, ‘\n‘) : ‘ ‘, ans[i]);42 printf("\n");43 }44 }45 return 0;46 }
UVa1623 Enter The Dragon (贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。