当前位置：首页 > news >正文

技能升级--二分例题

news 2025/7/15 10:44:24

1.题目

2. 暴力解法

直接遍历每一种情况，选择攻击力最高的解法

#include<iostream>
using namespace std;
int a[50010], b[50010];
int main()
{long long ans = 0;long long m;int n;cin >> n >> m;for (int i = 0; i < n; i++){cin >> a[i] >> b[i];}int i;//因为for循环外面的while里面还要用到while (m--){int max1 = 0;int maxsite=-1;for (i = 0; i < n; i++){if (a[i] > max1){max1 = a[i];maxsite = i;}}ans += max1;;a[maxsite] -= b[maxsite];}cout << ans << endl;return 0;
}

3.暴力法+优先队列

1.前情提要（优先队列）

优先队列是一种使用二叉堆优化结构的队列，分为最大值优先队列和最小值优先队列

最大值优先队列：

std::priority_queue<int> q;

最小值优先队列：

 priority_queue<int, vector<int>, greater<int>> minHeap;

他的时间复杂度只有O(log2n)

2.思路分析

通过使用对组改变优先队列的数据结构实现

3.代码呈现

#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
priority_queue<PII>q;//默认是大根堆，即最大值优先队列
PII p;
int main()
{long long m;int n;cin >> n >> m;for (int i = 0; i < n; i++){long long a, b;cin >> a >> b;q.push(PII(a, b));}long long ans = 0;while (m--){if (q.empty()){break;}p = q.top();q.pop();ans += p.first;p.first -= p.second;if (p.first > 0){q.push(p);}}cout << ans << endl;return 0;
}

3.二分优化

1.思路分析

这道题用二分做起来思辨性比较强，首先用作二分的数值便是一个难点，这里选用的是最后一次增加的最大值

2.代码呈现

#include<iostream>
#include<queue>
using namespace std;
long long m;
int n;
int a[100100], b[100100];
bool check(int mid)
{long long cnt = 0;for (int i = 0; i < n; i++){if (a[i] < mid){continue;}
//这里加1是因为首次增加攻击力的时候cnt += (a[i] - mid) / b[i] + 1;if (cnt >= m){return true;}}return false;
}
int main()
{cin >> n >> m;for (int i = 0; i < n; i++){cin >> a[i] >> b[i];}//二分int L = 1, R = 1000000;long long mid = 0;while (L <= R){//二分枚举最后一次能增加多少mid = (L + R) / 2;if (check(mid)){L = mid + 1;}else{R = mid - 1;}}//注意二分结束后得到的结果是R而不是midlong long attack = 0;long long cnt = m;for (int i = 0; i < n; i++){if (a[i] < R)continue;long long t = (a[i] - R) / b[i] + 1;attack += (a[i] * 2 - (t - 1) * b[i]) * t / 2;cnt -= t;}//最后的结果得出的t的总和一定是大于等于m的if(cnt<=0)cout << attack+cnt*R<< endl;else{cout << "-1" << endl;}return 0;
}