Split the Shopping Receipts
Autumn Tournament (2015)
Submission name: shop.cpp
Problem summary
For a receipt containing t products, the cheapest floor(t/k) products are free. Partition all chosen products into any number of receipts to minimize the total paid price.
Input
Integers n and k, then n integer prices.
Output
The minimum total payment.
Constraints
1 ≤ n ≤ 100000; 2 ≤ k ≤ 100; 1 ≤ price ≤ 10000.
Worked example
Original statement sample.
Input
5 2 20 10 100 40 10
Output
130
Solution analysis
- Sort all prices from largest to smallest. Place each consecutive block of k products on its own receipt. The last product of each complete block is free; pay for every other product, including an incomplete final block.
- The important choice is which products become free, not simply how many. Grouping expensive products together prevents a very cheap product from using a discount that could instead cover a more expensive one. In the sorted list, free indices are k, 2k, 3k, ... with 1-based indexing.
- For prices 100, 40, 20, 10, 10 and k=2, the first two blocks give free products 40 and 10. Pay 100+20+10=130. A single receipt would make only the two cheapest products free and cost 160.
Why it works
Consider the j most expensive free products in any valid partition. In any receipt, every paid product costs at least as much as every free product, and the receipt has at least k−1 paid products per free product. Therefore these j free products require at least j(k−1) products of no smaller price, so the j-th largest free price cannot exceed the price at global sorted position jk. The proposed blocks attain every such upper bound simultaneously, maximizing savings and minimizing payment.
Watch out. Sort in descending order. A receipt with fewer than k products has no free item. Applying the rule once to the whole purchase can be suboptimal.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<functional>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int count;
int blockSize;
cin>>count>>blockSize;
vector<int>prices(count);
for(int&price:prices){
cin>>price;
}
sort(prices.begin(),prices.end(),greater<int>());
long long payment=0;
for(int index=0;index<count;++index){
// The cheapest product in each complete k-product receipt is free.
if((index+1)%blockSize!=0){
payment+=prices[index];
}
}
cout<<payment<<'\n';
}