Contest2089

Problem E: Swipe

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 100 Solved: 15
[Submit][Status][Web Board]

Description

德鲁伊在炉石传说中是一个很稳定的职业，主流的卡组套路有咆哮德，城墙德以及让人很无奈的疲劳德。然而，大部分的卡组总都包括“横扫”这张德鲁伊的职业法术卡。

我们假定战场上的敌人数目不定，敌人的血量已知，我们想知道最少使用多少张“横扫”能消灭战场上所有敌人。

Input

第一行一个整数T( T<=100)，表示测试数据的组数。

接下来有T组数据，

每组数据第一行n （ n<=1000) ，表示战场上敌人的数目

第二行有n个数，表示每个敌人当前的血量 (数值不大于1000000)

Output

每组数据输出一个整数，占一行，表示消灭所有敌人所需的最少“横扫”数目

Sample Input

Sample Output

2
1

HINT

思路：每次攻击最大的；最大的减3，放入排序，标准线（即全体减去的数）加1；

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1648

转载请注明出处：寻找&星空の孩子

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <stack>
 5 #include <queue>
 6 #include <map>
 7 #include <set>
 8 #include <vector>
 9 #include <math.h>
10 #include <bitset>
11 #include <algorithm>
12 #include <climits>
13 using namespace std;
14  
15 #define LS 2*i
16 #define RS 2*i+1
17 #define UP(i,x,y) for(i=x;i<=y;i++)
18 #define DOWN(i,x,y) for(i=x;i>=y;i--)
19 #define MEM(a,x) memset(a,x,sizeof(a))
20 #define W(a) while(a)
21 #define gcd(a,b) __gcd(a,b)
22 #define LL long long
23 #define N 20005
24 #define MOD 1000000007
25 #define INF 0x3f3f3f3f
26 #define EXP 1e-8
27  
28 int a[1005],t,n;
29  
30 int main()
31 {
32     int i,j,k;
33     scanf("%d",&t);
34     W(t--)
35     {
36         scanf("%d",&n);
37         UP(i,0,n-1)
38         {
39             scanf("%d",&a[i]);
40         }
41         if(n==1)
42         {
43             if(a[0]%4)
44                 printf("%d
",a[0]/4+1);
45             else
46                 printf("%d
",a[0]/4);
47             continue;
48         }
49         sort(a,a+n);
50         int ans = 0;
51         W(a[n-1]-ans>0)
52         {
53             ans++;
54             a[n-1]-=3;
55             for(i = n-2; i>=0; i--)
56             {
57                 if(a[n-1]>a[i]||i==0)
58                 {
59                     int tem = a[i+1];
60                     a[i+1] = a[n-1];
61                     for(j=n-1; j>=i+3; j--)
62                         a[j]=a[j-1];
63                     a[i+2] = tem;
64                     break;
65                 }
66             }
67         }
68         printf("%d
",ans);
69     }
70  
71     return 0;
72 }
73  
74 /**************************************************************
75     Problem: 1648
76     User: aking2015
77     Language: C++
78     Result: Accepted
79     Time:812 ms
80     Memory:1492 kb
81 ****************************************************************/