Contest2089，contest
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
2
3
1 2 3
2
4
1 4 1 1
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\n",a[0]/4+1);
45 else
46 printf("%d\n",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\n",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 ****************************************************************/
