合并数列前m个数和

题目描述

有$nn$个线性序列，第$ii$个序列可以表示成$k_i\times x+b_{i}k\_i\times x+b\_i$的形式（x=0,1,2,…）。

现在询问将这些序列的数从小到大合并起来，前$mm$个数的和是多少（重复出现的数合并后也会多次出现）。

对于$100\mathrm{\%}100\backslash \%$的数据，保证$1\le n\le 100000,1\le m\le 100000,1\le k_i,b_i\le 10001\le n\le 100000,1\le m\le 100000,1\le k\_i,b\_i\le 1000$。

分析

二分答案

寻找$nn$个序列的数从小到大合并起来的最大值$MM$

判断$nn$个序列中值的个数总和是否

计算个数总和

序列满足条件的$xx$个数为

计算数值总和

等差数列求和

结果

假设找到的边界值$MM$计算个数为$kk$

那么$M+1M+1$一定存在且计算个数一定大于$m-km-k$个

所以最终结果为$sum(M)+(M+1)\ast (m-k)sum(M)+(M+1)*(m-k)$

边界

最小值为0

最大值为$10^5\ast 10^3+10^{3}10^5*10^3+10^3$

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,m,k[maxn],b[maxn];
ll calc(int x)
{
	ll res=0;
	for(int i=1;i<=n;i++){
		if(x>=b[i]) res+=(x-b[i])/k[i]+1;
	}
	return res;
}
ll sum(int x){
	ll res=0;
	for(int i=1;i<=n;i++)
	{
		if(x>=b[i]) {
			int num=(x-b[i])/k[i]+1;
			res+=1LL*(b[i]+b[i]+(num-1)*k[i])*num/2;
		}
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&k[i],&b[i]);
	scanf("%d",&m);
	int l=0,r=1e9;
	while(l+1<r){
		int mid=(l+r)/2;
		if(calc(mid)<=m)
			l=mid;
		else
			r=mid;
	}
	printf("%lld",sum(l)+1LL*(l+1)*(m-calc(l)));
}