AOJ_0227 Thanksgiving
問題
解法
貪欲法を使って、値段の高いものから順に袋に入れていけばいい。
つまり、値段の高い順にソートして、mで割りきれる番号の値段以外の合計を求める。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 1000; int yasai[MAX_N]; int main(){ int n, m; while(scanf("%d %d", &n, &m) && n){ int s = 0; for(int i = 0; i < n; i++) scanf("%d", &yasai[i]); sort(yasai, yasai + n); for(int i = 1; i <= n; i++){ if(!(i%m == 0)) s += yasai[n-i]; } printf("%d\n", s); } return 0; }