Approach
Sorting and greedy selection
For ABC208 C — Fair Candy Distribution, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 38 lines of C++ from the credited upstream file abc208_c.cpp.
- The implementation visibly relies on sequence storage, ordered lookup.
- 3 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <map>4#include <vector>5 6using namespace std;7 8int main() {9 long long N = 0, K = 0;10 cin >> N >> K;11 12 vector<long long> nums;13 map<long long, long long> nums_idx_map;14 map<long long, long long> nums_count_map;15 for (long long i = 0; i < N; i++) {16 long long a = 0;17 cin >> a;18 nums.push_back(a);19 nums_idx_map[i] = a;20 nums_count_map[a] = 0;21 }22 23 sort(nums.begin(), nums.end());24 25 long long base = K / N;26 long long remain = K - (N * base);27 for (auto& num : nums) {28 if (remain == 0) {29 break;30 }31 nums_count_map[num]++;32 remain--;33 }34 35 for (long long i = 0; i < N; i++) {36 cout << nums_count_map[nums_idx_map[i]] + base << endl;37 }38}