每日一练
技能升级
题目详细
小蓝最近正在玩一款 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 | 3 6 |
输出样例:
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
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;
}
1 |
|
管道
题目详细
有一根长度为 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 | 3 10 |
输出样例:
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
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;
}
1 |
|