贪心 HDOJ 5090 Game with Pearls-白红宇

贪心 HDOJ 5090 Game with Pearls

阅读量：7039 次

发布时间：2019-06-28

本文共 1215 字，大约阅读时间需要 4 分钟。

1 /* 2     题意：给n, k，然后允许给某一个数加上k的正整数倍，当然可以不加， 3         问你是否可以把这n个数变成1,2,3,...,n, 可以就输出Jerry, 否则输出Tom。 4     贪心：保存可能变成的值的方案数，当一个符合，其他所有可能方案减1 5     最大匹配 详细解释：http://blog.csdn.net/u012596172/article/details/40784773?utm_source=tuicool 6 */ 7 #include 
     
       8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 #include 
          
           13 #include 
           
            14 #include 
            
             15 #include 
             16 #include 
              
               17 #include 
               
                18 #include 
                
                 19 using namespace std;20 21 const int MAXN = 1e2 + 10;22 const int INF = 0x3f3f3f3f;23 int a[MAXN];24 int cnt[MAXN];25 int n, k;26 27 28 int main(void) //HDOJ 5090 Game with Pearls29 {30 //freopen ("A.in", "r", stdin);31 32 int t; scanf ("%d", &t);33 while (t--)34 {35 memset (cnt, 0, sizeof (cnt));36 scanf ("%d%d", &n, &k);37 for (int i=1; i<=n; ++i)38 {39 scanf ("%d", &a[i]);40 for (int j=a[i]; j<=n; j+=k)41 cnt[j]++;42 }43 bool win = true;44 for (int i=1; i<=n; ++i)45 {46 if (!cnt[i]) {win = false; break;}47 for (int j=i; j<=n; j+=k) cnt[j]--;48 }49 50 if (win) puts ("Jerry");51 else puts ("Tom");52 }53 54 return 0;55 }56 57 /*58 Jerry59 Tom60 */