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