y总不会告我侵权吧hh(y总的思路,我模拟了一遍,轻喷)
求赞!!!
请略过我这个菜鸡的暴力代码,收货tle一枚
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
vector<PII> hit;
int n, m;
long res;
int main()
{
cin >> n >> m;
while (n --)
{
int a, b;
cin >> a >> b;
hit.push_back({a, b});
}
while (m --)
{
sort(hit.begin(), hit.end());
if (hit[hit.size() - 1].first > 0)
{
res += hit[hit.size() - 1].first;
hit[hit.size() - 1].first -= hit[hit.size() - 1].second;
}
}
cout << res << endl;
return 0;
}
**思路****
1. 判断正确性
2. 优化
*Part 1 : 观察*
1. 要使最后的攻击力最大,选取的m个数一定是最大的那m个数
2. 每一个技能升级的过程都相当于一个首项为ai, 公差为bi, 项数为a[i]/bi的等差数列
*Part 2 : 正确性*
选取哪m个数,使得总和最大?
假设有total个数(1 <= total <= 1e11),将total个数从大到小排序,前m个数即为答案
反证法
如果选取的不是前m个数,假设选取了第m + 1个数,前面一定有一个数大于等于第m + 1个数,第m + 1位上的数一定不是答案
设前m个数的和为s,答案为res(res <= s,因为限制条件越多,值越小),能否取到’=’?
每次选取的是将等差数列的首项排序,选取其中的最大值,用完后及时更新首项,所以能取到’=’
*Part 3 : 分析,优化*
每次选取等差数列的首项排序后的最大值,只需要维护一个优先队列,O(Mlngn),肯定会TLE,随机就应该想如何优化
优化:多路归并,二分
设从大到小的第m个数是x
因为可能有多个相同的x,满足第m个数>=x, 总个数>= m(如果第m个数>= x + 1,总个数一定小于m)
所以具有二段性,即可以二分出来x
选取所有小于等于x的数,总个数一定满足>=m,所有>x的数,总个数一定不满足>= m
二分代码
int check(int mid)
{
LL res; // 总个数大于等于m(2e9),所以用long long存储
for (int i = 0; i < n; i ++)
{
res += (a[i] - mid) / b[i] + 1; // 计算每个等差数列中满足大于等于x的个数
}
return res >= m;
}
int l = 0, r = 1e6; // 初始攻击力最大为1e6
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
// 最后r即为要求的x
求和
二分出x的值后,将所有大于等于x的值相加,同时记录个数为cnt,因为可能有多个相同的x的值,所以答案res -= (cnt - m) * x;
LL res = 0, cnt = 0;
for (int i = 0; i < n; i ++)
{
if (a[i] >= r)
{
int n = (a[i] - x) / b[i] + 1; // 大于等于x的项数
int end = a[i] - (n - 1) * b[i]; // 求尾项
cnt += n;
res += (a[i] + end) * n / 2; // 等差数列求和
}
}
if (cnt > m) res -= (cnt - m) * r;
时间复杂度
check函数o(n); // n最大为1e5
二分函数总共O(nlngm); // m最大为1e6
大约为200万级别
补充
二分时,l为啥从0开始?
如果不存在任何一个大于等于1的数满足总数大于等于m,结果就会报错
设可供升级的总数为total(1 <= total <= 1e11),如果total小于m,即第m个数的值为0
**通俗来讲: r应该为0,可是最后二分出来结果r为1,r变大了**
for (int i = 0; i < n; i ++)
{
if (a[i] >= r)
{
int n = (a[i] - r) / b[i] + 1; // n变小
int end = a[i] - (n - 1) * b[i]; // end变大
cnt += n; // cnt变小
res += (a[i] + end) * n / 2; // res可能变大,也可能变小
}
}
if (cnt > m) res -= (cnt - m) * r; // 这种情况下cnt一定小于m, 所以这步不会执行
AC Code
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
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;
else r = mid - 1;
}
LL res = 0, cnt = 0;
for (int i = 0; i < n; i ++)
{
if (a[i] >= r)
{
int count = (a[i] - r) / b[i] + 1;
cnt += count;
int end = a[i] - b[i] * (count - 1); // 求末项
res += (LL)(a[i] + end) * count / 2;
}
}
if (cnt > m) res -= (cnt - m) * r;
cout << res << endl;
return 0;
}
*鄙人学时尚浅,欢迎大佬指正
*欢迎交流
转载自y总
如有侵权,联系删除hh
orz