codeforces 1119D Frets On Fire【预处理 + 二分】

题意：

给你一个长度为n的数组  0< n < 100000

每个数的大小为0~10^18

现在有q次查询

每次给你l r

意思为数组每个数每次加上同一个数字  得到一个新的数组 加的数字从l到r

请问这些数组中不同数字的个数为多少

题解：

这道题难度在暴力会tle，因为查询太多次

我们可以先预处理

将输入的数字先排序，处理得出相邻的数的差，再讲差值进行排序，二分找出比当前加的数字的区间大的差值有多少个

直接贪心求出答案

AC_code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll s[100005];
ll cc[100005];
ll sum[100005];
int main() {
//	std::ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	for(int i = 1; i <= n; i++) {
		cin>>s[i];
	}
	sort(s+1, s+n+1);
	for(int i = 1; i < n; i++) {
		cc[i] = s[i+1] - s[i];
	}
	cc[n] = 2e18;
	sort(cc+1, cc+n+1);//cha
	sum[0] = 0;
	for(int i = 1; i <= n; i++) {
		sum[i] = sum[i-1] + cc[i];
	}
	int q;
	cin>>q;
	ll l, r, len;
	ll ans = 0;
	while(q--) {
		cin>>l>>r;
		len = r - l + 1;
		ll ans = lower_bound(cc+1, cc+n+1, len) - cc - 1;
		printf("%lld ", sum[ans] + (ll)(n-ans)*len);
	}
	return 0;
}