百度松果菁英班--oj赛(第二次)

简介: 百度松果菁英班--oj赛(第二次)

一、小码哥剪绳子

**题目:**马上就要到文化节了,小码哥身为学生会的一员需要参与到道具制作。由于被分配到趣味拔河,小码哥需要切绳子,有N条绳子,它们的长度分别为L1,…,Ln。

如果从它们中切割出K条长度相同的绳子,这K条绳子每条最长能有多长?

/**
  输入格式:第一行两个整数N 和K ;接下来N行,每行一个整数代表每条绳子的长度 Li。
  输出格式:一个整数代表切割后每条绳子的最大长度。
  样例1   输入:4 11
                8
                7
                4
                5
      输出:2
  备注
对于100%的数据:0<Li≤100000,0 <n ≤100000,0<k≤10000 ;切割前后绳子的长度均为整数。
*/         
#include<bits/stdc++.h> 
using namespace std;
const int M = 1e5 + 5;
int L[M], N, K, l, r, mid, ans;
bool check(int num){
    int tmp = 0;
    for(int i = 1; i <= N; i++){
        tmp += L[i] / num;//根据最长的绳子判断出总条数
    }
    if(tmp >= K){//当条数大于等于K条,说明绳子取短了
        return true;
    }else{//当条数小于K条,说明绳子取长了
        return false;
    }
}
int main( )
{
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> L[i];
        r = max(r, L[i]);//找到最长的绳子
    }
    while(l <= r){
        mid = l + (r - l) / 2;
        if(check(mid)){
            l = mid + 1;
            ans = mid;//解决最后l和r的取值不明的情况
        }else{
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

二、咖啡品鉴师小码哥

**题目:**这天,小码哥想要喝一杯咖啡,现在有 n种调料,这杯咖啡只可以加入其中的 m种。小码哥在得知所有的 n种调料后,用计算机算出了所有调料消耗的时间ci以及调料的美味度vi。小码哥要喝到求和符vi/求和符ci最大的咖啡,也就是单位时间的美味度最大的咖啡。

求和符表示求和,所以求和符vi/求和符ci表示美味度的总和除以消耗时间的总和。

/**
  输入格式:第一行为两个整数n,m ,表示调料种数和能加入的调料数;接下来两行,每行为n个数,第一行第i个整数表示美味度ui ,第二行第i个整数表示时间ci。
  输出格式:一个整数表示小码哥喝的咖啡的最大`求和符vi/求和符ci`,保留三位小数。
  样例1   输入:3 2
                1 2 3
                3 2 1
      输出:1.667
  备注
数据范围:20%: 1≤n ≤5; 50%: 1≤n≤10; 80%: 1≤n≤50; 100%: 1≤n ≤200,1≤m≤n,1≤c[团], v[2]≤10000 ;保证答案不超过1000。
*/         
#include<bits/stdc++.h> 
using namespace std;
int n, m;
double v[205], c[205], t[205];
bool check(double x){
    double sum = 0;
    //v[i] = xc[i] -> v[i] - xc[i] = 0
    for(int i = 1; i <= n; i++){
        t[i] = v[i] - x * c[i];
    }
    sort(t + 1, t + n + 1);//升序
    for(int i = n; i >= n - m + 1; i--){
        sum += t[i];//取最大的m种
    }
    if(sum > 0){
        return true;
    }else{
        return false;
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> c[i];
    }
    double l = 0, r = 1001;//由于答案不超过1000
    while(r - l > 1e-5){//答案取的范围最小为0.0001
        double mid = l + (r - l) / 2.0;
        if(check(mid)){//当v[i] - xc[i] > 0时,mid取小了
            l = mid;
        }else{
            r = mid;
        }
    }
    printf("%.3lf", l);
    return 0;
}

三、均分糖果

**题目:**小码哥有n个手下,位置从1到n ,他们坐成一排,每个人有ai个糖果,每个人只能把糖果送给左右两个人,由于坐在1和n位置上的是术士,他们可以通过技艺,相互传递糖果,每人每次传递一个糖果代价为1。

数据保证糖果一定可以被均分,不会出现小数情况。

/**
  输入格式:第一行一个正整数n ≤le3,表示手下的个数;接下来n行,每行一个整数ai,表示第i个手下得到的糖果的颗数。
  输出格式:求使所有人获得均等糖果的最少代价。
  样例1   输入:4
                9
                8 
                17 
                6
      输出:8
  备注
    其中:1≤n ≤1e3,0≤ai ≤ 1e5
*/         
#include<bits/stdc++.h> 
using namespace std;
int n, a[1005], x[1005], sum, avg, ans; 
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }
    avg = sum / n;
    //等价于一个圈,对于第一位 -> avg = a[1] + xn - x1(自己加上第n位给的减去给第二位的) 
    //可以推导出avg = a[n] + x(n-1) - xn -> xn = a[n] - avg - x(n-1)
    //将给出的xn求和 <==> sum(|xn|) = x(n-1) + avg - a[n]  <==>  花费的代价
    for(int i = 1; i <= n; i++){
        x[i] = x[i - 1] + avg - a[i];
    }
    sort(x + 1, x + 1 + n);//花费代价升序
    数轴距离模型 --> 取中间值时该点到其它点的距离之和最短
    //等价于本题的取排序后中间的人的糖果数,分给其它人后相加的代价最小 
    //x[(n + 1) / 2] -> 向下取整    n / 2 + 1 -> 向上取整
    for(int i = 1; i <= n; i++){
        ans += abs(x[(n + 1) / 2] - x[i]); 
    }
    cout << ans;
    return 0;
}

四、持盾

**题目:**n个盾卫在切尔诺伯格上寻找遇难者,但是非常不巧遇见了黑蛇,黑蛇用她的火焰攻击盾卫,在一片火海中,盾卫决定排成一列,在这火焰风暴中撤退。红色箭头为黑蛇的攻击方向,显然盾卫们(黑色的方块)在排成一列的情况下,可以受到最少的攻击。每个盾卫有力量和质量两个属性,对于每个盾卫来说,他的风险值为他前面的所有盾卫的质量w之和 减去他的力量s。其中质量之和不包括他自己的质量。

问如何排盾卫的顺序,使得盾卫中最大的风险值最低?

/**
  输入格式:第一行一个正整数n ;第二行到第1+n行,每行两个正整数,表示盾卫的质量和力量。
  输出格式:输出一个使盾卫中最大的风险值最低的排序下,最大的风险值。
  样例1   输入:3
                10 3
                2 5
                3 3
      输出:2
  备注
其中:1≤n≤50000,1≤w≤100000,1 ≤s≤1000000000
*/         
#include<bits/stdc++.h> 
using namespace std;
const int N = 5e4 + 5;
struct NODE{
    int w, s, sum;
}node[N];
//当w1在前面,假设此时排序最优   ...w1|w2  -> max(all - s1, all + w1 - s2)
//当w2在前面  ...w2|w1 -> max(all -s2, all + w2 -s1)   此时w1前 <  w2前
//依次比较可以推断出风险值 -> all + w1 -s2 < all + w2 - s1 -> w1 + s1 < w2 + s2
bool cmp(NODE a, NODE b){
    return a.sum < b.sum;//风险值升序
}
int n, ans = -0x3f3f3f3f, presum;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> node[i].w >> node[i].s;
        node[i].sum += node[i].w + node[i].s;//计算风险总值
    }
    sort(node + 1, node + n + 1, cmp);
    for(int i = 1; i <= n; i++){
        presum += node[i - 1].w;//除去自身重量
        ans = max(ans, presum - node[i].s);
    }
    cout << ans;
    return 0;
}

五、活动安排

**题目:**小码哥又被安排去处理公司大厅事项了,公司只有一个大厅,但有许多的活动需要召开,所以需要提前预约,该公司有n个部门,每个部门会举办一个活动。每个部门会向小码哥上报他们预期使用大厅的时间区间 (a,b)(开区间),小码哥会根据时间做安排,一个时间只能有一个活动在召开,活动一旦开始必须结束才能进行下一个活动。

小码哥想要尽可能多的满足活动的召开,于是请你来帮忙安排活动。

/**
  输入格式:第一行一个整数n,代表部门的个数;接下来的n行,每行两个整数a,b,代表时间区间.
  输出格式:输出一个整数代表能够召开的最大活动个数。
  样例1   输入:4
                1 3
                4 6
                2 5
                1 7
      输出:2
  备注
    其中: 1≤n ≤500000,0≤a<b≤10^9
*/         
#include<bits/stdc++.h> 
using namespace std;
const int N = 5e5 + 5;
int n, ans;
struct NODE{
    int l, r;
}node[N];
bool cmp(NODE a, NODE b){
    return a.r < b.r;//按活动结束时间升序
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> node[i].l >> node[i].r;
    }
    sort(node + 1, node + 1 + n, cmp);
    int temp = 0;//定义一个临时变量来存储可行的结束时间
    for(int i = 1; i <= n; i++){
        //下一个活动的开始时间大于上一个活动的结束时间
        if(node[i].l >= temp){
            temp = node[i].r;
            ans++;
        }
    }
    cout << ans;
    return 0;
}

六、甜品供应

**题目:**小码哥的C个手下有着不同的甜食喜好程度,而对于一个甜食来说,可以用一个数字vi来表示他的甜度。小码哥的手下对于一定区间的甜度的甜品表示喜欢。对于一个编号为i的手下,他的甜品喜爱区间为[li,ri],但如果超过或小于这个区间的甜品则表示讨厌,并影响当天的上班心情。小码哥为了使上班的工作效率最大,购置了一批甜品,有L种,甜度为vi的甜品有numi 个。

请问小码哥最多可以使多少人吃到喜欢的甜品?

/**
  输入格式:第1行:两个空格分隔的整数:C和L;第2…C+1 行:每行用两个整数描述手下i的甜度要求:li和ri;第C+2·….C+L+1行:每行两个整数描述某一种甜品的甜度和个数: vi和numi 。
  输出格式:带有整数的单行,表示可以使最多的手下吃到他们喜欢的甜品的人数。
  样例1   输入3 2
                3 10
                2 5
                1 5
                6 2
                4 1
      输出:2
  备注
提示:其中:1≤L,C ≤2500,1 ≤li, ri, vi, numi≤10^5
*/         
#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 5;
struct PEOPLE{
    int l, r;
    bool operator<(const PEOPLE &a) const{
        if(l == a.l){//当最低甜度相同时,最大甜度先的排前
            return r < a.r;
        }
        return l < a.l;//以最低甜度升序
    }
}people[N];
struct SWEET{
    int v, num;
    bool operator>(const SWEET &a) const{
        return v > a.v;//甜度降序
    }
}sweet[N];
int C, L, cnt[N], ans;
//定义小根堆,根据甜度来构造小根堆
priority_queue<SWEET, vector<SWEET>, greater<SWEET>> q;
int main(){
    cin >> C >> L;
    for(int i = 1; i <= C; i++){
        cin >> people[i].l >> people[i].r;
    }
    sort(people + 1, people + 1 + C);//根据开始时间排序
    for(int i = 1; i <= L; i++){
        cin >> sweet[i].v >> sweet[i].num;
        cnt[sweet[i].v] += sweet[i].num;
        q.push(sweet[i]);//将甜品入小根堆
    }
    for(int i = 1; i <= C; i++){
        //将小根堆的甜度,从小依次出堆和每一个手小的最小甜度比较
        //若甜度小于手下的最小甜度就将该甜品出堆
        while(!q.empty() && q.top().v < people[i].l){
            q.pop();
        }
        //当甜度大于手下最小的甜度&甜度小于手下的最大甜度
        if(!q.empty() && q.top().v <= people[i].r){
            ans++;//满足人数加一
            cnt[q.top().v]--;//甜品数量减一
            if(cnt[q.top().v] == 0){
                q.pop();//甜品分完出堆
            }
        }
    }
    cout << ans;
    return 0;
}

七、斐波那契数列的组合

**题目:**给定一个正整数n,请写一个函数MinFibonacciNumbers ,返回和为n的斐波那契数字的最少数目。

斐波那契数列F1=1 F2=1 Fn= Fn-1+Fn-2,n > 2保证一定存在解。

/**
  输入格式:第一行输入正整数n。
  输出格式:输出满足要求的数字的最少数目。
  样例1   输入:19
      输出:3
  备注
    其中: 1≤n≤109;
    样例:19=1+5+13,所以至少需要3个数字。
*/         
#include<bits/stdc++.h> 
using namespace std;
int MinFibonacciNumbers(int k){
    vector<int> v;
    v.push_back(1);
    v.push_back(1);
    while(1){//将斐波那契数列1e9中的数字全部入容器
        if(v[v.size() - 1] + v[v.size() - 2] > 1e9){
            break;
        }
        v.push_back(v[v.size() - 1] + v[v.size() - 2]);
    }
    int cnt = 0;
    for(int i = v.size() - 1; i >= 0; i--){
        if(k >= v[i]){
            cnt += k / v[i];//看最大的数有几个符合相加起来
            k -= k / v[i] * v[i];//原来的数减去向下取整的数
        }
        if(k == 0){
            break;
        }
    }
    return cnt;
}
int main(){
    int n; 
    cin >> n;
    cout << MinFibonacciNumbers(n);
    return 0;
}

八、小码哥的布阵指挥

**题目:**小码哥手上有n个部队,驻扎在一条马路上,可以把这个马路看作一条x轴,小码哥的指挥所在原点,第i个部队在a[i]的位置,现在重新布置部队的位置,设布置后的位置为b[i],要求b[i]≥a[i],且每个部队之间的距离大于等于X。

说明:部队从第1个开始按顺序进行处理。一旦处理完,位置就不再发生变化。所以你需要做出对于每只部队来说,当前情况下最优解(当前情况指,序号在他之前的部队已经更新过后的情况),即在满足上述条件下,部队离小码哥越近越好。

/**
  输入格式:第一行两个整数n,X ;第二行n个整数,表示a[i]。
  输出格式:一行,输出b[列],空格分开。
  样例1   输入:4 11
        1 21 11 7
      输出:1 21 32 43
    样例2   输入:4 10
                1 21 11 7
                输出:1 21 11 31
  备注
    其中: 1≤n ≤1000,1 ≤x, a[i], b[i]≤10^6
*/         
#include<bits/stdc++.h> 
using namespace std;
#define N 1005
int n, X, a[N], b[N];
int main(){
    cin >> n >> X;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    b[1] = a[1];//题目要求从第一个按顺序处理
    for(int i = 2; i <= n; i++){
        //插入排序,将数组a依次判断做升序处理
        sort(a, a + i);
        //这里的插入排序是从前面开始依次比较
        for(int j = 1; j < i; j++){
            //依次与前面的对比位置,距离小了
            if(fabs(a[i] - a[j]) < X){
                a[i] = a[j] + X;
                b[i] = a[i];
            }else{//距离符合从新给b[i]数组赋值即可
                b[i] = a[i];
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout << b[i] << " ";
    }
    return 0;
}

九、活动分组

**题目:**小码哥组织一次团建活动,共有n 人参加。活动分为A、B两个项目,每个项目都需要两人组队参加。假设每个人有两个能力值 a,b分别表示对A、B两个项目的擅长程度,为了使活动圆满进行,小码哥希望每一组的两个人A能力值之和等于B能力值之和。

请你帮忙计算是否有一种分组的可能满足小码哥的想法。

/**
  输入格式:输入共三行,第一行一个偶数n∈[2,1×10^5]表示总人数;第二行n个正整数表示每个人A项目的能力值;第三行n个正整数表示每个人B项目的能力值。
  输出格式:一行,如果存在这样的分组输出YES,否则输出NO
  样例1   输入:6
                1 2 3 4 5 6
                6 5 4 3 2 1
      输出:YES
  备注
    第一个和第六个一组,第二个和第五个一组,第三个和第四个一组,这样每组的A项目能力值之和均为7,B项目能力值之和均为7。
*/         
#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 5;
int n, a[N], b[N], c[N];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
    }
    //a[i] + a[j] = b[i] + b[j]
    //a[i] - b[i] = b[j] - a[j]
    //(a[i] - b[i]) + (a[j] - b[j]) = 0
    for(int i = 1; i <= n; i++){
        c[i] = a[i] - b[i];//求两项目的能力差值
    }
    sort(c + 1, c + n + 1);//能力差值升序
    //推导出最高位加最低位等于0
    for(int i = 1; i <= n; i++){
        //只需要考虑异常情况即可
        if(c[i] + c[n - i + 1] != 0){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

十、外卖递送

**题目:**小码哥又被安排去建设外卖站了,所有居民的居住地点ai都在一条x轴上,小码哥为了使送外卖移动的距离最短,现在在选择设置外卖站的位置。小码哥请你帮忙计算把站建在何处,可以使得站到每家居民的距离之和最小?

注意:不保证居民的居住地点ai唯一,即可以两个居民的居住地点相同,允许外卖站设在居民点。

/**
  输入格式:第一行一个整数n,表示居民的居住地点个数;第二行n个整数a1~an。
  输出格式:输出一个整数,表示距离之和的最小值。
  样例1   输入:4
        6 2 9 1
      输出:12
  备注
其中:对于100%的数据: 1≤n ≤100000, abs(ai)≤10000000
*/         
#include<bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 1e5;
ll n, a[N], ans;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);//将房子位置升序
    //数轴距离模型,取中间值,到各点的距离之和最短
    for(int i = 1; i <= n; i++){
        ans += abs(a[(n + 1) / 2] - a[i]);
    }
    cout << ans;
    return 0;
}

记录每一个学习瞬间

目录
相关文章
|
算法 Java 机器人
百度松果菁英班--3月日常练习题-1
百度松果菁英班--3月日常练习题-1
52 0
|
Java C++ Python
快讯:LeetCode中国正式上线《剑指Offer》题目,刷题真方便了!
近日,LeetCode中国[1]上线了一个全新的分类模块 LCOF “剑指 Offer[2]”。
6242 0
快讯:LeetCode中国正式上线《剑指Offer》题目,刷题真方便了!
|
人工智能
天梯赛-L1-064 估值一亿的AI核心代码 (20 分)--2019全国CCCC天梯赛L1题解
天梯赛-L1-064 估值一亿的AI核心代码 (20 分)--2019全国CCCC天梯赛L1题解
368 0
|
6月前
|
人工智能 测试技术 C++
蓝桥杯15届第二次模拟赛C/C++详解
蓝桥杯15届第二次模拟赛C/C++详解
147 0
|
人工智能 算法 程序员
百度松果菁英班--oj赛(第三次)
百度松果菁英班--oj赛(第三次)
75 0
|
存储 AI芯片
百度松果菁英班--oj赛(第五次)
百度松果菁英班--oj赛(第五次)
74 0
|
机器学习/深度学习 人工智能 安全
百度松果菁英班--oj赛(第四次)
百度松果菁英班--oj赛(第四次)
87 0
|
人工智能 BI
百度松果菁英班--oj赛(第一次)
百度松果菁英班--oj赛(第一次)
64 0
|
机器学习/深度学习 安全
2023年百度之星题解
2023年百度之星题解
|
机器学习/深度学习
HZU蓝桥杯校内第二次选拔赛题解
HZU蓝桥杯校内第二次选拔赛题解
76 0