首页 > 其他分享 >2024AcWing蓝桥杯集训·每日一题-二分

2024AcWing蓝桥杯集训·每日一题-二分

时间:2024-03-02 19:55:30浏览次数:28  
标签:10 攻击力 int 教室 mid 蓝桥 订单 一题 2024AcWing

1.[AcWing503.借教室]

题目描述

在大学期间,经常需要租借教室。
大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。
教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。
面对海量租借教室的信息,我们自然希望编程解决这个问题。
我们需要处理接下来 \(n\) 天的借教室信息,其中第 \(i\) 天学校有 \(r_i\) 个教室可供租借。
共有 \(m\) 份订单,每份订单用三个正整数描述,分别为 \(d_j,s_j,t_j\),表示某租借者需要从第 \(s_j\) 天到第 \(t_j\) 天租借教室(包括第 \(s_j\) 天和第 \(t_j\) 天),每天需要租借 \(d_j\) 个教室。
我们假定,租借者对教室的大小、地点没有要求。
即对于每份订单,我们只需要每天提供 \(d_j\) 个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。
借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。
如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。
这里的无法满足指从第 \(s_j\) 天到第 \(t_j\) 天中有至少一天剩余的教室数量不足 \(d_j\) 个。
现在我们需要知道,是否会有订单无法完全满足。
如果有,需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 \(n,m\),表示天数和订单的数量。
第二行包含 \(n\) 个正整数,其中第 \(i\) 个数为 \(r_i\),表示第 \(i\) 天可用于租借的教室数量。
接下来有 \(m\) 行,每行包含三个正整数 \(d_j,s_j,t_j\),表示租借的数量,租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。
天数与订单均用从 \(1\) 开始的整数编号。

输出格式

如果所有订单均可满足,则输出只有一行,包含一个整数 \(0\)。
否则(订单无法完全满足)输出两行,第一行输出一个负整数 \(−1\),第二行输出需要修改订单的申请人编号。

数据范围

\(1≤n,m≤10^6,\)
\(0≤r_i,d_j≤10^9,\)
\(1≤s_j≤t_j≤n\)

输入样例
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
输出样例
-1
2
解题思路

首先每份订单需要教室是区间性质的,那么可以考虑前缀和和差分进行订单的预处理,处理得出每天需要的教室数量。
该问题需要求解是否存在订单无法满足,且教室分配是按照订单顺序,那么我们可以二分最后一个满足分配要求的订单,即该订单 \(i\) 及其前面的订单都可以满足。

C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
typedef long long LL;

int n, m;
int w[N], d[N], s[N], t[N];
LL b[N];

bool check(int k) {
    memset(b, 0, sizeof b);
    // 差分
    for (int i = 1; i <= k; i++) {
        b[s[i]] += d[i];
        b[t[i] + 1] -= d[i];
    }
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += b[i];
        if (sum > w[i]) // 需大于供
            return false;
    }
    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]); // 每天供给的教室数量
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]); // 订单
    int l = 0, r = m;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    if (r == m) puts("0");
    else printf("-1\n%d\n", r + 1);
    return 0;
}

2.[AcWing5407.管道]

题目描述

有一根长度为 \(len\) 的横向的管道,该管道按照单位长度分为 \(len\) 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。
一开始管道是空的,位于 \(L_i\) 的阀门会在 \(S_i\) 时刻打开,并不断让水流入管道。
对于位于 \(L_i\) 的阀门,它流入的水在 \(T_i\)(\(T_i≥S_i\))时刻会使得从第 \(L_i−(T_i−S_i)\) 段到第 \(L_i+(T_i−S_i)\) 段的传感器检测到水流。
求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

输入的第一行包含两个整数 \(n,len\),用一个空格分隔,分别表示会打开的阀门数和管道长度。
接下来 \(n\) 行每行包含两个整数 \(L_i,S_i\),用一个空格分隔,表示位于第 \(L_i\) 段管道中央的阀门会在 \(S_i\) 时刻打开。

输出格式

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

数据范围

对于 \(30\%\) 的评测用例,\(n≤200\),\(S_i,len≤3000\);
对于 \(70\%\) 的评测用例,\(n≤5000\),\(S_i,len≤10^5\);
对于所有评测用例,\(1≤n≤10^5\),\(1≤S_i,len≤10^9\),\(1≤L_i≤len\),\(L_{i−1}<L_i\)。

输入样例
3 10
1 1
6 5
10 2
输出样例
5
解题思路

二分时间,具体思路见代码注释。

C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
typedef long long LL;

int n, len;
int L[N], S[N];
PII a[N];

bool check(int mid) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (S[i] <= mid) { // 打开时刻 ≤ mid
            int t = mid - S[i];
            int l = max(1, L[i] - t), r = min((LL) len, (LL) L[i] + t);
            a[cnt++] = {l, r}; // 统计通水区间
        }
    }
    sort(a, a + cnt);
    // 区间合并
    int st = -1, ed = -1;
    for (int i = 0; i < cnt; i++) {
        if (a[i].first <= ed + 1) ed = max(ed, a[i].second);
        else st = a[i].first, ed = a[i].second;
    }
    return st == 1 && ed == len;
}

int main() {
    scanf("%d%d", &n, &len);
    for (int i = 1; i <= n; i++) scanf("%d%d", &L[i], &S[i]);
    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;
}

3.[AcWing4656.技能升级]

小蓝最近正在玩一款 \(RPG\) 游戏。
他的角色一共有 \(N\) 个可以加攻击力的技能。
其中第 \(i\) 个技能首次升级可以提升 \(A_i\) 点攻击力,以后每次升级增加的点数都会减少 \(B_i\)。\(⌈A_i / B_i⌉\)(上取整)次之后,再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 \(M\) 次技能,他可以任意选择升级的技能和次数。
请你计算小蓝最多可以提高多少点攻击力?

输入格式

输入第一行包含两个整数 \(N\) 和 \(M\)。
以下 \(N\) 行每行包含两个整数 \(A_i\) 和 \(B_i\)。

输出格式

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

数据范围

对于 \(40\%\) 的评测用例,\(1≤N,M≤1000\);
对于 \(60\%\) 的评测用例,\(1≤N≤10^4\),\(1≤M≤10^7\);
对于所有评测用例,\(1≤N≤10^5\),\(1≤M≤2×10^9\),\(1≤A_i,B_i≤10^6\)。

输入样例
3 6
10 5
9 2
8 1
输出样例
47
解题思路

最简单的思路,想要攻击力总和最大,将所有技能的攻击力预处理出来利用大根堆,每次都取最大的那一个。
那么如何优化?
可以二分第 \(M\) 的攻击力,判断是否存在多余 \(M\) 个攻击力 \(≥\) 该值。

C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;

int n, m;
int a[N], b[N];

bool check(int mid) { // 二分攻击力
    LL cnt = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] >= mid) // 可以进行技能加点
            cnt += (a[i] - mid) / b[i] + 1; // 加点次数
    return cnt >= m;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; 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 sum = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= r) {
            int c = (a[i] - r) / b[i] + 1;
            int ed = a[i] - (c - 1) * b[i];
            cnt += c;
            // 等差数列求和
            sum += (LL) (a[i] + ed) * c / 2;
        }
    }
    // 减去可能多加的攻击力
    printf("%lld\n", sum - (cnt - m) * r);
    return 0;
}

4.[AcWing102.最佳牛围栏]

题目描述

农夫约翰的农场由 \(N\) 块田地组成,每块地里都有一定数量的牛,其数量不会少于 \(1\) 头,也不会超过 \(2000\) 头。
约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 \(F\) 块地,其中 \(F\) 会在输入中给出。
在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式

第一行输入整数 \(N\) 和 \(F\),数据间用空格隔开。
接下来 \(N\) 行,每行输入一个整数,第 \(i+1\) 行输入的整数代表第 \(i\) 片区域内包含的牛的数目。

输出格式

输出一个整数,表示平均值的最大值乘以 \(1000\) 再 向下取整 之后得到的结果。

数据范围

\(1≤N≤100000\)
\(1≤F≤N\)

输入样例
10 6
6 
4
2
10
3
8
5
9
4
1
输出样例
6500
解题思路

二分平均值。

C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n, f;
int a[N];
double s[N];

bool check(double mid) {
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i] - mid; // 减去平均值求前缀和
    double minv = 0;
    for (int i = 0, j = f; j <= n; i++, j++) {
        minv = min(minv, s[i]);
        // 区间的值大于等于 0
        if (s[j] >= minv) return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &f);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    double l = 0, r = 2000;
    while (r - l > 1e-6) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%d\n", (int) (r * 1000));
    return 0;
}

标签:10,攻击力,int,教室,mid,蓝桥,订单,一题,2024AcWing
From: https://www.cnblogs.com/Cocoicobird/p/18049141

相关文章

  • 第十一届蓝桥杯试题E:排序
    目录题目分析验证代码题目对一个字符串,对它进行冒泡排序使其为升序,例如:对于lan,排序成aln需要交换一次(只能交换相邻的两个字母),对于qiao,排序成aioq就需要交换4次。请找出冒泡排序时恰好需要交换100次的字符串,如果有多个字符串满足条件,则找出最短的那个,如果有多个满足条件而且......
  • P8680 [蓝桥杯 2019 省 B] 特别数的和
    暴力秒了#include<bits/stdc++.h>#defineintlonglong//开longlong是个好习惯usingnamespacestd;boolbaozi(intx){while(x){intt=x%10;if(t==2||t==0||t==1||t==9)//数位判断{returntrue;......
  • 蓝桥杯2022年第十三届省赛真题-技能升级(中)
    目录题目题解:暴力题解:优化题目题解:暴力思路:枚举每一个Ai,并一直减去Bi,直到小于零为止,即为该技能所能增加的点数的集合。将每一个选择存进res中,并排序选择前M大的技能点即可。#首先,a-b加入列表,循环a/b次;其次,对列表排序,取前M个数进行求和a,b=map(int,input().split())#读入......
  • 2024 蓝桥杯模拟赛3(div1+div2)
    2024蓝桥杯模拟赛3(div1+div2)P8834[传智杯#3决赛]序列简单的模拟,数据范围很小,暴力即可点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+5;voidsolve(){ lln,k,a[N],cnt=0; cin>>n>>k; for(inti=1;i<=n;i++)c......
  • P8647 [蓝桥杯 2017 省 AB] 分巧克力
    题目链接:小巧克力的边长一定在\(1\sim10^5\)之间。答案为在\(1\sim10^5\)之间找一个最大的数,使得所有\(h[i]/a*w[i]/a\)的和\(\geqslantk\)即可。#include<cstdio>#include<algorithm>constintN=1e5+10;intn,k,h[N],w[N];boolcheck(inta)......
  • (蓝桥)递归与递推
    1、对于 scanf printf和cincout按照10^5来划分使用 递归实现指数型枚举 https://www.acwing.com/problem/content/94/ #include<iostream>#include<cstring>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=17;intn;inta[N];......
  • 第十四届蓝桥杯个人题解
    a幸运的数主要是思路 遍历1-100000000每一层循环,首先将其每一位分到数组里,并记录位数,如果是偶数位再接着往下,比较前半和后半是否相等:通过加减最后结果是否为零来判断intmain(){  intnum=0;  for(inti=1;i<100000000;i++)  {    ints[9]={0};......
  • 备战蓝桥
    0地宫取宝-蓝桥云课(lanqiao.cn)对于该问题,首先是个迷宫问题,于是先考虑暴力求解,对于暴力来说,有这样一种方法:对于任何一点来说,都可以进行选或者不选,然后当走到终点时如果符合条件则答案加$1$,这样做的时间复杂度是$2^n也就是2^50$,很明显得不到满分.既然是迷宫那......
  • 2024 蓝桥杯模拟赛3(div1+div2)
    P8834[传智杯#3决赛]序列\(O(N^2)\)枚举defread():returnmap(int,input().split())n,k=read()a=list(read())res=0foriinrange(n):forjinrange(i):ifa[i]*a[j]<=k:res+=1print(res)P8780[蓝桥杯2022省......
  • 2024 蓝桥杯模拟赛3(div1+div2)
    题目A.暴力枚举#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn,k;cin>>n>>k;vector<int>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];......