题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
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+=(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 c=(a[i]-r)/b[i]+1;
int end=a[i]-(c-1)*b[i];
cnt+=c;
res+=(ll)(a[i]+end)*c/2;
}
}
cout<<res-(cnt-m)*r<<'\n';
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla