优先队列暴力(TLE)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
priority_queue<PII> heap;
int a[N], b[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
cin >> a[i] >> b[i];
heap.push({a[i], i});
}
int res = 0, id = 0;
while (m -- ) {
res += heap.top().first;
id = heap.top().second;
heap.pop();
a[id] -= b[id];
heap.push({a[id], id});
}
cout << res;
return 0;
}
二分优化
找到符合条件的最大的mid,即Max~mid之间的数是所有数中最大的m个
若x <= mid,则说明可以取的数的个数 >= m
若x > mid,则说明可以取的数的个数 < m
找到此mid,每个数序列的次数就为首项-mid / 公差 + 1
计算出每个序列的次数相加即为总次数
求和可用等差数列求和公式 (首项+末项)* 项数 / 2
最终减去多余的mid的和,因为等于mid的值可能有多个
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N], b[N];
bool check(int mid)
{
LL res = 0;
for (int i = 0; i < n; i ++ ) {
if (a[i] >= mid) {
res += (LL)(a[i] - mid) / b[i] + 1; // 计算每个序列选到的数的个数
}
}
return res >= m;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> a[i] >> b[i];
int l = 0, r = 1e6;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid; // 数小了,将l往前提
else r = mid - 1; // 数大了,将r往后提
}
LL res = 0, cnt = 0, num = 0, end = 0;
for (int i = 0; i < n; i ++ ) {
if (a[i] >= r) {
num = (a[i] - r) / b[i] + 1; // 计算每个序列选到的数的个数
end = a[i] - (num - 1) * b[i]; // 末项
res += (LL)(a[i] + end) * num / 2; // 等差序列求和
cnt += num; // 计算总的次数
}
}
cout << res - (cnt - m) * r; // 减去多余的等于mid的值的和
return 0;
}