AOJ : 0227 - Thanksgiving (お客様大感謝祭)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0227&lang=jp
日本語の問題文なので説明省略です.

アルゴリズム

高い商品から順番に袋に詰めていって, 袋が一杯になったときは, 一番最後に入れた商品の値段を割引します.
そのあとは, また新しい袋に入れていきます.
これを商品を全て袋に詰め終えるまで繰り返します.

プログラム

#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
  int n,m;

  while(cin>>n>>m,n){
    int t[n];
    for(int i=0;i<n;i++){
      cin>>t[i];
    }
    sort(t,t+n);
    reverse(t,t+n);

    int ans = 0;
    for(int i=0;i<n;i+=m){
      int sum = 0;
      for(int j=i;j<n && j<i+m;j++){
        sum += t[j];
      }
      if(i+m <= n) sum -= t[i+m-1];
      ans += sum;
    }
    cout<<ans<<endl;
  }

  return 0;
}