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;
}