AcWing 4656. 技能升级
原题链接
困难
作者:
计划好明天
,
2024-03-04 21:25:43
,
所有人可见
,
阅读 17
//二段性在哪里
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100010;
int n,m;
int a[N],b[N];
//找攻击力大的加,加够6次即可(暴力)
//假设x是第m个数,每一组的都是等差数列(竖着写出来每一组),然后最大值先从最上面找
//找到一个最大值之后删除它,最大值所在的数组的第二个数就变成了第一个数
//再从第一个数里面找最大值
//x可能不只一个,所以>=x的数有>=m个(画横线图)
//<x(也就是<=x-1)的数,有<=m个
//所以贪心+二分
//从大到小排序(因为是等差数列)
bool check(int mid)//二分找的是第m个数对应的x
{
LL res=0;
for(int i=0;i<n;i++)//列举的每一个等差数列
{
if(a[i]>=mid)//a[i]是指每一个等差数列的头
//比mid大的数
res+=(a[i]-mid)/b[i]+1;//计算项数
}
return res>=m;
}
int main()
{
//已经全局变量定义过了,这里再写一遍int n,m;会让check有问题
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i]>>b[i];
int l=0,r=1e6;
while(l<r)//二分来找x
{
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
//二分之后r就是要找的x
LL res=0,cnt=0;//cnt记录项数
//cout<<r<<' ';
//这里相当于对每个数列进行运算,求和就好了
//知道a[i],和b[i],也就是说知道首相和公差,就相当于知道了整个等差数列
for (int i = 0; i < n; i ++ )
if (a[i] >= r)//这里是一个等差数列一个等差数列的来看
{
int c = (a[i] - r) / b[i] + 1;
int end =a[i] - (c - 1) * b[i];
//cout<<"c:"<<c<<' '<<"a[i]:"<<a[i]<<' '<<"end:"<<end<<' ';
cnt += c;
res += (LL)(a[i] + end) * c / 2;
}
//之所以这样输出而不是直接输出res,是因为减去多余的数
//比如满足>=x的数有7个,而题目只需要5个,那么这里的res是求的7个的(x重复)
//所以答案需要减去两个最后2个数(从大到小排列)
//(比如把题目所给样例8后面的1改成2)
//加上这两行看一下区别
//cout<<"cnt:"<<cnt<<' ';
//cout<<"res:"<<res<<' ';
printf("%lld\n", res - (cnt - m) * r);
//错误思想
/*for(int i=0;i<n;i++)
{
int c=(a[i]-r)/b[i]+1;//计算a[i]到x之间有几个数(项数)
LL end=(LL)a[i]-(c-1)*b[i];//计算末项
res*=(a[i]+end)/2;
}
cout<<res;*/
return 0;
}