请求题目加强数据
查看原帖
请求题目加强数据
362174
线段树小王子楼主2020/7/20 19:46

P2639题目数据太水了

我写了一个多次贪心都80pts了

希望管理可以加强数据@chen_zhe

//Greedy+bublesort
#include<stdio.h>
#include<stdbool.h>
int s[505], n;
inline long long max(long long a, long long b) {
	if(a < b) return b;
	else return a;
}
void bubble_sort() {
	int i, j;
	for(i = 1; i <= n; i++) {
		int flag = 0;
		for(j = 1; j < n-i; j++)
			if(s[j] > s[j+1]) {
					int t = s[j];
					s[j] = s[j+1];
					s[j+1] = t;
					flag = 1;
			}
		if(!flag) break;
	}
}
inline long long Greedy1(int H) { //贪心策略 1 
	int i;
	long long ans = 0;
	for(i = 1; i <= n; i++)  {
		if(s[i] <= H) {
			ans += s[i];
			H -= s[i];
		} 
		else break;
	}
	return ans;
}
inline long long Greedy2(int H) { //贪心策略 2
	int i;
	long long ans = 0;
	for(i = n; n >= 1; i--) {
		if(s[i] <= H) {
			ans += s[i];
			H -= s[i];
		} 
		if(H == 0) break;
	}
	return ans;
}
inline long long Greedy3(int H) { //贪心策略3
	int i, j;
    long long ans = 0;
	bool vis[505];
	for(i = 1; i <= n; i++) {
		for(j = 1; j < n; j++)	
			if((s[j+1] > H && s[j] <= H && !vis[j]) || (j == n-1 && s[n] <= H && !vis[n])) {
				ans += s[i];
				H -= s[i];
				vis[j] = 1;
			}
		if(H == 0) break;
	} 
	return ans; 
}			 
int main() {
	int H, i;
	scanf("%d%d", &H, &n);
	for(i = 1; i <= n; i++)
		scanf("%d", &s[i]);
    if(n == 1) { 
        printf("%d", s[1]);
        return 0;
    }
	bubble_sort();
	long long ans = Greedy1(H);
	ans = max(ans, Greedy2(H));
	ans = max(ans, Greedy3(H));
	printf("%lld\n", ans); 
	return 0;
} 
2020/7/20 19:46
加载中...