第一题 3974. K 个元素的最大总和
- 题解
按从大到小依次选k个元素，判断mul的正负决定累加时是否乘以mul，mul减一。
其中，数组长度为10^5所以每次去最大元素用暴暴力遍历会超，我这里用大跟堆实现。下面给出小跟堆代码。
void up(int i, vector<int> & a) { int t = i >> 1; if (!t) return; if (a[t] < a[i]) { swap(a[t], a[i]); up(t, a); } } void down(int i, int n, vector<int>& a) { int l = i * 2; int r = i * 2 + 1; if (r < n) { int k = r; if (a[l] > a[r]) { k = l; } if (a[i] < a[k]) { swap(a[i],a[k]); down(k, n, a); } } }else if (l < n) { if (a[i] < a[l]) { swap(a[i], a[l]); down(l, n, a); } } }第二题