题解 CF1006B 【Polycarp's Practice】

## 贪心 ### 思路：贪前k个最大值 开一个结构体，记录id,num（下标，数值）。 sort排序两遍，第一遍排序数值（降序）找前k大的数，全部选中。 第二遍按下标排序，每次记前面一次选中的数的下标，当再次找到选中值的时候，用当前下标i减去上一次下标p即为答案。 #### 注意：最后一次输出不是i-p,而是n-p（后面也要包含） ### $Code$ ```cpp #include <cstdio> #include <algorithm> using namespace std; const int N = 2005; struct Node { int num, id; } a[N]; bool cmp1(Node x, Node y) {//第一遍排序 return x.num > y.num; } bool cmp2(Node x, Node y) {//第二遍排序 return x.id < y.id; } int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i].num), a[i].id = i; sort(a + 1, a + 1 + n, cmp1); int ans = 0; for (int i = 1; i <= k; i++) { // printf("%d\n", ans); ans += a[i].num;//前i个最大值一定能被选中 a[i].num = -2147483647;//选中并附极小值，防止和其他值撞车 } sort(a + 1, a + 1 + n, cmp2); printf("%d\n", ans); int p = 0; for (int i = 1; i <= n; i++) { if (a[i].num == -2147483647 && k) {//遍历到选中值 if (k == 1) {//特判最后一次 printf("%d\n", n - p); k--; } else { printf("%d ", i - p); p = i; k--; } } } return 0; } ```