Codeforce 522C - Chicken or Fish? 模拟

71 阅读 0 评论 47 点赞

我是靠谱客的博主洁净酸奶，最近开发中收集的这篇文章主要介绍Codeforce 522C - Chicken or Fish? 模拟，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

//思路：因为题目是要求求出所有可能被选完的 dish，所以当之前乘客所选 dish 不确定时，将所有 dish 的数量均减一（做法是记录下来不确定的 dish 的数量）；当出现第一个顾客 QAQ（不开心）的时候，说明在他之前至少有一个 dish 已经被选完了，这时候就需要利用不确定的 dish 的数量优先构造出一个被选完的 dish（注意到之后被选择的 dish 一定不能再此刻被选完）

//感觉这题要是题目读懂了就没什么难度了......弱渣这题读了好半天 Orz

 1 #include "bitsstdc++.h"
 2 using namespace std;
 3 int T;
 4 int m, n;
 5 int cnt[100005], cnt_pre[100005], sum, sum_pre, res[100005];
 6 bool dish_pre[100005];
 7 
 8 int main()
 9 {
10     int i;
11     scanf("%d", &T);
12     while(T--) {
13         sum = sum_pre = 0;
14         memset(dish_pre, 1, sizeof(dish_pre));
15         memset(res, 0, sizeof(res));
16         scanf("%d%d", &m, &n);
17         for(i = 1; i <= n; ++i) {
18             scanf("%d", &cnt[i]);
19             cnt_pre[i] = cnt[i];
20         }
21         int dish, QAQ;
22         bool stop = 0;
23         for(i = 1; i <= m - 1; ++i) {
24             scanf("%d%d", &dish, &QAQ);
25             if(dish)
26                 --cnt[dish];
27             else
28                 ++sum;
29             if(stop) {
30                 dish_pre[dish] = 0;
31                 continue;
32             }
33             if(QAQ) {
34                 dish_pre[dish] = 0;
35                 stop = 1;
36                 continue;
37             }
38             if(dish)
39                 --cnt_pre[dish];
40             else
41                 ++sum_pre;
42         }
43 
44         if(stop) {
45             int rem = 0;
46             for(i = 1; i <= n; ++i) {
47                 if(dish_pre[i] && cnt_pre[i] <= sum_pre) {
48                     res[i] = 1;
49                     rem = max(rem, sum - cnt_pre[i]);
50                 }
51             }
52 
53             for(i = 1; i <= n; ++i) {
54                 if(cnt[i] <= rem) {
55                     res[i] = 1;
56                 }
57             }
58         }
59         else {
60             for(i = 1; i <= n; ++i) {
61                 res[i] = cnt[i] <= sum;
62             }
63         }
64 
65         for(i = 1; i <= n; ++i) {
66             putchar(res[i]? 'Y': 'N');
67         }
68         puts("");
69     }
70 }