Loner John 的博客
0%

csuoj-算法-PIPI打怪

发表于 更新于 分类于 Valine：

题目

解题思路

利用贪心思想，先死的怪一定血量最低的。
先按血量高低进行排序，再遍历一遍。

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int ans=0;
            int n=scanner.nextInt();
            int [] array=new int[n];
            for (int i = 0; i < n; i++) {
                array[i]=scanner.nextInt();
            }
            Arrays.sort(array);
            for (int i = 0,flag=0,add=0; i < array.length; i++) {
                if(array[i]<=flag-2){
                    flag-=2;
                }
                if (array[i]>flag){
                    add=(array[i]-flag)/2+(array[i]-flag)%2;
                    flag+=add*2;
                    ans+=add;
                }
                flag+=2;
            }
            System.out.println(ans);
        }
    }
}

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

int aarray[10001];
int main(void){
	int n;
	while(scanf("%d",&n)!=EOF){
		int ans=0;
		for(int i=0;i<n;i++){
			scanf("%d",&aarray[i]);
		}
		sort(aarray,aarray+n);
		for(int i=0,flag=0,add=0;i<n;i++){
			if(aarray[i]<=flag-2){
				flag-=2;
			}
			if(aarray[i]>flag){
				add=(aarray[i]-flag)/2+(aarray[i]-flag)%2;
				flag+=add*2;
				ans+=add;
			}
			flag+=2;
		}
		printf("%d\n",ans);
	}
	return 0;
}