技能升级

题目详细

小蓝最近正在玩一款 RPG游戏。

他的角色一共有 N个可以加攻击力的技能。

其中第 i个技能首次升级可以提升 Ai点攻击力，以后每次升级增加的点数都会减少 Bi。

⌈Ai/Bi⌉（上取整）次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 M次技能，他可以任意选择升级的技能和次数。

请你计算小蓝最多可以提高多少点攻击力？

输入格式

输入第一行包含两个整数 N和 M。

以下 N行每行包含两个整数 Ai和 Bi。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 40%的评测用例，1≤N,M≤1000；
对于 60%的评测用例，1≤N≤104，1≤M≤107；
对于所有评测用例，1≤N≤105，1≤M≤2×109，1≤Ai,Bi≤106。

输入样例：

1
2
3
4
3 6
10 5
9 2
8 1

输出样例：

1
47

题解

思路

这道题采用二分和多路归并的思想。
二分体现在加多少攻击力上，它的范围是0~1e6，不断缩小范围就行。如何缩小，需要推导公式，首先我们想象加攻击力是n个数组（将数组中的数看作等差数列，每个数列其实存的是一种攻击力，但是每种攻击力会等差缩小），每个数组都是从大到小排序的，现在我们要从n个数组中每次取出最大的放到一个集合里，最后求出集合中前m个数的和。既然是等差数列，那么选择的等差数列首尾相加乘以项数除以2，将这些等差数列加起来就是最后要求的值。只要遍历的数大于等于第m个数，那么就放到集合中。最后输出的话需要减去多加的部分，以为有重复的数（这些数都比第m个数大），所以会导致多加。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
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() {
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++) {
		scanf("%d%d",&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;
		}
	}

	printf("%lld\n",res-(cnt-m)*r);
	return 0;
}

管道

题目详细

有一根长度为 len的横向的管道，该管道按照单位长度分为 len段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

一开始管道是空的，位于 Li的阀门会在 Si时刻打开，并不断让水流入管道。

对于位于 Li的阀门，它流入的水在 Ti（Ti≥Si）时刻会使得从第 Li−(Ti−Si)段到第 Li+(Ti−Si)段的传感器检测到水流。

求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

输入的第一行包含两个整数 n,len
，用一个空格分隔，分别表示会打开的阀门数和管道长度。

接下来 n行每行包含两个整数 Li,Si，用一个空格分隔，表示位于第 Li段管道中央的阀门会在 Si时刻打开。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 30%的评测用例，n≤200，Si,len≤3000；
对于 70%的评测用例，n≤5000，Si,len≤105；
对于所有评测用例，1≤n≤105，1≤Si,len≤109，1≤Li≤len，Li−1<Li。

输入样例：

1
2
3
4
3 10
1 1
6 5
10 2

输出样例：

1
5

题解

思路

这道题的思路就是二分+区间合并
二分在于管道中每一段中间的传感器都检测到有水流的最早时间。因为要求的时间范围再1~2e9，那么总有一刻是每段传感器都能检测到水流。那么根据这个二段性来求出这个时间。判断条件为，当检测的时间小于要求的时间，那么根据题目的式子，可以求出水流的区间，给区间排序，如果区间的与下一个区间相邻（只相差1）且下个区间的右端点大于该区间的右端点，那么就合并成一个区间。否则就符合完全重合。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int,int> PII;
const int N=100010;
typedef long long LL;
int n,len;
PII w[N],q[N];//w[]存储阀门的位置和水流开启的时间，q[]存储的是二分之后每个阀门对应区间 

bool check(int mid){
	int cnt=0;
	for(int i=0;i<n;i++){
		int L=w[i].x,S=w[i].y;
		if(S<=mid){
			int t=mid-S;
			int l=max(1,L-t),r=min((LL)len,(LL)L+t);
			q[cnt ++] = {l,r}; 
		}	
	}
	sort(q,q+cnt);
	
	int st=-1,ed=-1;
	for(int i=0;i<cnt;i++){
		if(q[i].x<=ed+1) ed=max(ed,q[i].y);
		else st=q[i].x,ed=q[i].y;
	}
	return st==1&&ed==len;
}

int main(){
	scanf("%d%d",&n,&len);
	for(int i=0;i<n;i++){
		scanf("%d%d",&w[i].x,&w[i].y);
	}
	
	int l=0,r=2e9;
	while(l<r){
		int mid=(LL)l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	
	printf("%d\n",r);
	return 0;
}