百度松果菁英班--oj赛（第一次）

蔚落 2024-03-24 17:44 26阅读 0赞

#### 文章目录 ####

*   *  一、甜品配置
     *  二、第k小的距离
     *  三、MT2091 竹鼠发瓜子（二）
     *  四、水温调节
     *  五、摘果子
     *  六、能量供应
     *  七、小码哥的跳棋游戏新编
     *  八、sort
     *  九、名次并列
     *  十、逆序对

### 一、甜品配置 ###

\*\*题目：\*\*小码哥的上司是一个爱吃甜品的人，他给了小码哥v的经费，去购买m个甜品，这些甜品有bi的价格，和 ai的甜度，上司希望甜度越高越好，但是他比较忙，没有时间来确定所有甜品的甜度，只会去看M个甜品的中位数的甜度，于是小码哥决定在买M个甜品,总价格不超过v的情况下，尽可能的让中位数大。如果m是偶数，那么中位数就是中间两个甜品的甜度的平均值。

/**
    	输入格式:第一行三个数u，n，m，分别代表经费，甜品数量以及需要买的甜品数量;接下来n行，每行两个数a，bi，分别代表甜品甜度以及价格。其中: n≤le5，1≤m≤n，ai ≤le9，u≤1e9，bi≤u。
    	输出格式:输出一个整数，最大的中位数。
    	样例1   输入：20 5 3
    				3 5
    				5 6
    				8 7
    				10 6
    				15 10
    			输出：8
    	备注
    提示:n ≤1e5，1 ≤m≤n，ai≤1e9，v ≤1e9，bi ≤ v。本题数据保证一定有解。
    */         
    #include <bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    struct SWEET{
        int a,b;
    }sw[N];
    int v,n,m,l,r,mid,ans,sum1[N],sum2[N];
    
    bool cmp(SWEET s1,SWEET s2){return s1.a<s2.a;}
    int main(){
        cin>>v>>n>>m;
        for(int i=1;i<=n;i++) cin>>sw[i].a>>sw[i].b;
        sort(sw+1,sw+n+1,cmp);
    
        priority_queue<int> q1,q2;
        for(int i=1;i<=n;++i){
            q1.push(sw[i].b);
            sum1[i] = sum1[i-1] + sw[i].b;
            if(q1.size() > m/2-1+m%2)
                sum1[i] -= q1.top(),q1.pop();
        }
        for(int i=n;i>0;i--){
            q2.push(sw[i].b);
            sum2[i] = sum2[i+1] +sw[i].b;
            if(q2.size()>m/2) sum2[i] -= q2.top(),q2.pop();
        }
    
        if(m%2){
            for(int i=n-m/2;i>=m/2+1;i--)
                if(sum1[i-1]+sum2[i+1]+sw[i].b<=v){
                    cout<<sw[i].a;
                    break;
                }
        }else{
            for(int i=m/2;i<=n-m/2;i++){
                l=i+1,r=n-m/2+1;
                int tmp=0;
                while(l<=r){
                    mid = l+(r-l)/2;
                    if(sum1[i-1]+sum2[mid]+sw[i].b<=v)
                        l = mid+1,tmp=mid;
                    else
                        r = mid-2;    
                }
                if(tmp>i) ans = max(ans,sw[i].a+sw[tmp].a);
            }
            cout<<ans/2<<endl;
        }
        return 0;
    }

### 二、第k小的距离 ###

\*\*题目：\*\*给定一个整型数组(n个)表示的位置，请返回所有数对中第k小的距离。一对(A,B)的距离表示A和B之间的绝对差值。

/**
    	输入格式:第一行输入两个整型n和k(n ≤10^6，0 <k <n(n -1)/2);第二行输入整型数组。
    	输出格式:输出一个整型。
    
    
    	样例1   输入：3 1
    				1 3 1
    			输出：0
    */
    //c++
    #include<bits/stdc++.h> 
    using namespace std;
    typedef long long ll;
    ll a[100005];
    int n,k;
    
    bool ck(int num){
        
        int cnt = 0;
        for(int r1 = 0; r1 < n; r1++){
        
            int l1 = 0;
            while(a[r1] - a[l1] > num && r1 > l1){
        
               l1++;
            }
            cnt += r1 - l1;//累加
        }
        return cnt >= k;//累加值大说明找大了
    }
    
    int main() {
        
        cin >> n >> k;
        for(int i = 0; i < n; i++){
        
            cin >> a[i];
        }
        sort(a,a+n);
        ll r=a[n-1]-a[0];
        ll l=0;
        while(l < r){
        
            ll mid = l + (r - l) / 2;
            if(ck(mid)){
        
                r = mid;
            }else{
        
                l = mid + 1;
            }
        }
        cout << l;
        return 0;
    }
    
    //java
    import java.util.Scanner;
    import java.util.*;
    
    class Main {
        
        static int[] a = new int[1000005];
        static int n, k, mid, ans = 0;
    
        static boolean check(int num){
        
            int c = 0;
            for(int r1 = 0; r1 < n; r1++){
        
                int l1 = 0;
                while(a[r1] - a[l1] > num && r1 > l1){
        
                    l1++;
                }
                c += r1 - l1;//累加
            }
            return c >= k;//如果c大说明找大了
        }
    
        public static void main(String[] args) {
        
            Scanner input = new Scanner(System.in);
            // code here
            n = input.nextInt();
            k = input.nextInt();
            int l = 0, r;
            for(int i = 0; i < n; i++){
        
                a[i] = input.nextInt();
            }
            Arrays.sort(a,0,n);
            r = a[n - 1] - a[0];//排序后，max - min
            while(l -r <= 0){
        
                mid = l + (r - l) / 2;
                if(check(mid)){
        
                    r = mid - 1;
                    ans = mid;
                }else{
        
                    l = mid + 1;
                }
            }
            System.out.printf("%d", ans);
            input.close();
        }
    }

### 三、MT2091 竹鼠发瓜子（二） ###

\*\*题目：\*\*小码哥一口气买了一包有m颗瓜子的qiaqia瓜子，现在要把这些瓜子分给n只竹鼠。每只竹鼠都有一个瓜子的期望值，如果没有达到竹鼠的期望值，竹鼠就会生气，竹鼠生气的程度等于它少得到瓜子数的平方。小码哥要合理分配糖果，使竹鼠们生气的程度之和最小。

/**
    	输入格式:第一行两个整数m和n;第二行n个整数，表示竹鼠的期望值。
    	输出格式:输出一个整数，竹鼠们的最小生气总数。
    
    	样例1   输入: 10 4
    				4 5 2 3
    			输出：4
    */
    //c++
    #include<bits/stdc++.h> 
    using namespace std;
    #define ll long long
    const int N = 1e5 + 5;
    ll m, n, a[N], ans;
    
    int main( )
    {
        cin >> m >> n;
        ll sum = 0;
        for(int i = 0; i < n; i++){
            cin >> a[i];
            sum += a[i];
        }
        sum -= m;
        sort(a, a + n);
        for(int i = 0; i < n; i++){
            //当少得瓜子数相等时，其平方的和最小
            ll s = min(a[i], sum / (n - i));// 生气时少得的瓜子数
            ans += s * s;
            sum -= s;
        }
        cout << ans;
        return 0;
    }
    //java
    import java.util.Scanner;
    import java.util.*;
    
    class Main {
    
       public static void main(String[] args) {
    
        Scanner input = new Scanner(System.in);
        // code here
        int m = input.nextInt();
        int n = input.nextInt();
        int[] a = new int[100005];
        int sum = 0, ans = 0;
        for(int i = 0; i < n; i++){
            a[i] = input.nextInt();
            sum += a[i];
        }
        sum -= m;//欠的瓜子
        Arrays.sort(a, 0, n);
        for(int i = 0; i < n; i++){
            int s = Math.min(a[i], sum / (n - i));//找最小生气时少得的瓜子数
            ans += s * s;
            sum -= s;
        }
        System.out.printf("%d", ans);
        input.close();
       }
    }

### 四、水温调节 ###

\*\*题目：\*\*小码哥家里的浴缸里有一个冷水龙头和一个热水龙头，流出的水温分别是t1和t2;它们的流速最大是每秒x1和x2个单位，并且可以调节到0至最大流速间的任意一个整数速度。假如两个龙头的流速分别是y1和y2( 0≤y1,y2 ≤10^6)，那么最终的水温就是`t=(t1*y1 + t2*y2)/(y1+y2)`。现在，你要安排两个水龙头的流速，满足:1.最终水温不低于t0 ;2.在满足上一条的前提下，水温尽可能接近t0;3.在满足上一条的前提下，总流速尽可能大。

/**
    	输入格式:一行五个整数t1, t2, x1, x2, t0;其中: 1≤t1≤t0≤t2≤10^6，1≤x1,x2≤10^6
    	输出格式:输出一行两个数表示y1和y2 。
    
    	样例1   输入: 10 70 100 100 25
    			输出：99 33
    	备注  一定要仔细注意数据范围。
    */
    #include<bits/stdc++.h>
    using namespace std;
    int t1, t2, x1, x2, t0;
    double best = 0x3f3f3f3f, t, ans1, ans2;
    
    int main()
    {
    	cin >> t1 >> t2 >> x1 >> x2 >> t0;
    	double y1 = x1, y2 = x2;
    	while(y1 >= 0 && y2 >= 0)//流数小于0退出
    	{
    		t = double(t1 * y1 + t2 * y2) / (y1 + y2);//转double
            //温度低的情况
    		if(t < t0) {
                y1--;//降低冷水流数
                continue;
            }
            //这里如果写成if(t<best)best=t的话会在精度上出问题
    		if(t - t0 < best){
                best = t - t0;
                ans1 = y1;
                ans2 = y2;
            }
            //温度高的情况
    		y2--;
    	}
    	cout<<ans1<<' '<<ans2<<endl;
    	return 0;
    }

### 五、摘果子 ###

\*\*题目：\*\*在一个果园中，有n种果树，他们分布在一条数轴上，有独立的坐标。小码哥被奖励了许多果子，但是这些果子需要他自己去摘，小码哥摘一次果子需要1分钟。现在小码哥在第一颗果树下开始行走，从i棵走到i＋1棵需要ti的时间。如果小码哥选择在这棵果树下摘，那么第一个1分钟将会摘下ai的果子，第二次摘将摘下ai - di个果子，第三次将摘下ai一2 \* di个果子，以此类推。但是小码哥的时间有限，只有t的总时间来摘果子。请你帮助他算出，可以摘下的最大果子数是多少?

/**
    	输入格式:第一行输入正整数n，t ;第二行n个数，表示第一次可以摘的果子数ai ;第三行n个数，表示每次摘减少的可摘数di ;第四行n-1个数，表示数之间的间隔行走时间ti 。
    	输出格式:输出一个数，最大的果子数。
    
    	样例1   输入: 2 12
    				10 6
                    2 5
                    2
    			输出：37
    	备注  提示:所有变量均为正整数。其中: 1<t ≤ le5，1<n ≤25，1≤a，d，ti≤ 1e5
    */
    #include<bits/stdc++.h> 
    
    using namespace std;
    int const maxn = 10005;
    struct TREE {
        int num, id;//第一次可摘的果子数和树的ID
        //原来num是按从小到大排，当存储用优先队列时会相反,会按num从大到小排
        bool operator<(const TREE &x) const{
            return num < x.num; 
        }
    }tree[maxn];
    int n, t, di[maxn], ti[maxn], ans;
    priority_queue<TREE> q;
    
    int main( )
    {
        cin >> n >> t;
        for(int i = 1; i <= n; i++){
            cin >> tree[i].num;
            tree[i].id = i;
        }
        for(int i = 1; i <= n; i++){
            cin >> di[i];//递减果子数
        }
        for(int i = 1; i < n; i++){
            cin >> ti[i];//树间行走时间
        }
        for(int i = 1; i <= n; i++){
            t -= ti[i -1];//减去树与树之间行走的时间
            int now = 0;//从第一颗数到第n颗数所摘的果子数
            while(!q.empty()){//将上一次循环的优先队列清空
                q.pop();
            }
            for(int j = 1; j <= i; j++){
                q.push(tree[j]);//将每次循环到的数入队列
            }
            for(int j = 1; j <= t; j++){
                TREE s;
                s = q.top();//将头队列入树
                if(s.num > 0){
                    now += s.num;//累加果子数
                }
                s.num -= di[s.id];//递减==下次可摘的果子数
                q.pop();//将摘过的树出队列
                q.push(s);//将递减后的树入队列
            }
            ans = max(ans, now);//取循环过程中最大的果子数
        }
        cout << ans;
        return 0;
    }

### 六、能量供应 ###

\*\*题目：\*\*最近小码哥迷上了一款建造管理类游戏，游戏中的设施需要能量塔提供能量，设施运行时需要一定数量的能量塔在附近才能运作，不同的设施需要的能量塔的数量以及能链接到能量塔的范围也不一样，超出设施链接范围的能量塔无法为设施提供能量，不同设施可以重复利用同一座能量塔。现在小码哥修建了一条长为n的道路来放置能量塔，但能量塔的修建成本稍高，小码哥不想花太多时间收集资源建造过多能量塔，现在小码哥用一个区间\[s,e\]告诉你每个设施链接到能量塔的有效范围，以及每个设施需要的能量塔数量t，请你告诉他最少修建多少个能量塔即可让所有设施运作?

/**
    	输入格式:两个正整数n，b，表示道路的长度和设施的数量;接下来b行每行三个正整数s，e，t，表示设施的链接范围的起始和结尾以及需要的能量塔数量。
    	输出格式:一个整数，表示需要的最少的能量塔的数量。
    
    	样例1   输入: 8 3
    				1 3 1
                    4 5 1
                    3 3 1
    			输出：2
    	备注  其中:1≤n ≤105，1≤b≤104，1≤s;≤e ≤n，1≤t ≤e -S;＋1注意，能量塔不能重叠放置。
    */
    #include<bits/stdc++.h> 
    using namespace std;
    const int N = 1e5 + 7;
    struct TOWER{
        int s, e, t;//起始、结尾、能量塔数量
    }tower[N];
    int n, b, ans;
    bool build[N];//默认每一个节点上没有能量塔
    bool cmp(TOWER a, TOWER b){
        return a.e < b.e;//以结尾节点从大到小排序
    }
    int main(){
        cin >> n >> b;
        for(int i = 1; i <= b; i++){
            cin >> tower[i].s >> tower[i].e >> tower[i].t;
        }
        //以结尾节点从大到小排序
        sort(tower + 1, tower + 1 + b, cmp);
        for(int i = 1; i <= b; i++){
            int count = 0;
            for(int j = tower[i].s; j <= tower[i].e; j++){
                if(build[j]){//节点上有能量塔
                    count++;
                }
            }
            if(count >= tower[i].t){//区域内的能量塔大于等于所需能量塔
                continue;
            }
            //区域内的能量塔不足时，从结尾节点开始，从右往左建能量塔
            for(int j = tower[i].e; j >= tower[i].s; j--){
                if(!build[j]){
                    build[j] = true;
                    count++;
                    ans++;
                    if(count == tower[i].t){
                        break;
                    }
                }
            }
        }
        cout << ans;
        return 0;
    }

### 七、小码哥的跳棋游戏新编 ###

\*\*题目：\*\*小码哥喜爱跳棋。跳棋游戏在一条直线上，一共n个位置(1 ~n)，每个位置有3个状态:0表示没有棋子，1表示红棋子，2表示蓝棋子。在起始的点（坐标为0）没有棋子。小码哥的棋子自然是能通过没有棋子的位置。当面前有1个棋子时，小码哥可以直接跳过。当有两个及以上不同颜色棋子连在一起时，小码哥的棋子是跳不过去的。这时候，就要花费能量，破坏掉一些棋子，才能跳过。但小码哥的棋子是经过升级的，如果一连串相同颜色的棋子在一起时，小码哥是可以直接跳过的。已知破坏一枚棋子需要花费一点能量。现在求小码哥到达终点(坐标为n＋1)需要花费至少多少能量?

/**
    	输入格式:第一行包含一个正整数n ;第二行n个整数a;(1≤i≤n)，表示棋盘的状态。
    	输出格式:一个整数，输出最小耗费的能量数。
    
    	样例1   输入: 5
    				0 1 1 0 0
    			输出：0
    	备注  其中:3≤n≤10^5
    */
    #include<bits/stdc++.h> 
    using namespace std;
    const int N = 1e5 + 7;
    int n, ans,a[N];
    
    int main( )
    {
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        for(int i = 2; i <= n; i++){
            //当连续有棋子，且不同颜色
            if(a[i] && a[i - 1] && a[i] != a[i - 1]){
                a[i] = 0;//摧毁棋子
                ans++;
            }
        }
        cout << ans;
        return 0;
    }
    
    //java
    import java.util.Scanner;
    import java.util.*;
    
    class Main {
        static int[] a = new int[100005];
        static int ans = 0;
       public static void main(String[] args) {
    
        Scanner input = new Scanner(System.in);
        // code here
        int n = input.nextInt();
        for(int i = 1; i <= n; i++){
            a[i] = input.nextInt();
        }
        for(int i = 2; i <= n; i++){
            //当连续有棋子，且不同颜色
            if(((a[i] == 1 && a[i - 1] == 2) || (a[i] == 2 && a[i - 1] == 1)) && a[i] != a[i - 1]){
                a[i] = 0;
                ans++;
            }
        }
        System.out.print(ans);
        input.close();
       }
    }

### 八、sort ###

\*\*题目：\*\*或许在某个平行宇宙，会存在一种语言，使用的字母和英语一样，但字典序不一样。给出1个字典序和1个字符串，将字符串按新字典序排序。

/**
    	输入格式:第一行26个互不相同的小写字母，表示新型字典序;第二行1个字符串，表示待排序字符串。
    	输出格式:1个字符串代表答案。
    
    	样例1   输入: qwertyuiopvmnbcxzasdfghjkl
    				 peace
    			输出：eepca
    	备注  其中:1≤字符串长度≤100000，字符串只包含小写字母。
    */
    #include<bits/stdc++.h> 
    
    using namespace std;
    const int N = 1e5 + 5;
    struct NODE {
        char c;//字符
        int x;//权值
        bool operator<(const NODE &B) const{
            return x < B.x;//根据权值升序
        }
    }ans[N];
    int a[30], len;
    string s1, s2;
    int main(){
        cin >> s1;
        for(int i = 0; i < 26; i++){
            a[s1[i] - 'a'] = i;//给对应的字母赋上权值
        }
        cin >> s2;
        len = s2.length();
        for(int i = 0; i < len; i++){//给结构体赋值
            ans[i].c = s2[i];
            ans[i].x = a[s2[i] - 'a'];
        }
        sort(ans, ans + len);//权值升序
        for(int i = 0; i < len; i++){
            cout << ans[i].c;
        }
        return 0;
    }

### 九、名次并列 ###

\*\*题目：\*\*有n个人参加比赛，其中分数排名前k的人将被选入下一轮（选入下一轮的人分数必须为正)，特别的，如果几个人分数相同且刚好并列处于第k名（或是并列k-i名，但是全部算入后选入下一轮的人数超过k人），这几个人都将被选入下一轮。小码哥请你输出进入下一轮的人数？

/**
    	输入格式:输入一共两行，第一行是两个数n, k( 1 ≤k ≤n ≤1e5 ) ;第二行有n个数，分别参加比赛的人的分数a1, a2,.. . ,an( 0≤ai ≤100 )。
    	输出格式:输出进入下一轮的人数。
    
    	样例1   输入: 8 5
    				 7 5 10 7 9 8 7 5
    			输出：6
    */
    #include<bits/stdc++.h> 
    
    using namespace std;
    const int N = 1e5 + 5;
    int n, k, a[N], ans;
    bool cmp(int a, int b){
        return a > b;//降序
    }
    int main(){
        cin >> n >> k;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        sort(a + 1, a + 1 + n, cmp);
        for(int i = 1; i <= k; i++){
            //当前k名有分数为0的，记录不为0的人数
            if(a[i] > 0){
                ans++;
            }else{//出现有0分的，输出人数，退出
                cout << ans;
                return 0;
            }
        }
        for(int i = k + 1; i <= n; i++){
            if(a[i] == a[k]){//k名后分数相同的人数
                ans++;
                continue;
            }
        }
        cout << ans;
        return 0;
    }
    
    //java  运行超时
    import java.util.Scanner;
    import java.util.*;
    
    public class Main {
    
       public static void main(String[] args) {
    
        Scanner input = new Scanner(System.in);
        // code here
        int n = input.nextInt();
        int k = input.nextInt();
        Integer[] a = new Integer[100005];
        int ans = 0;
        for(int i = 1; i <= n; i++){
            a[i] = input.nextInt();
        }
        //利用外部比较器升序排序
    	MyCompare mc = new MyCompare();
        Arrays.sort(a, 1, n + 1, mc);
        
        for(int i = 1; i <= k; i++){
            //当前k名有分数为0的，记录不为0的人数
            if(a[i] > 0){
                ans++;
            }else{//出现有0分的，输出人数，退出
                System.out.print(ans);
                return;
            }
        }
        for(int i = k + 1; i <= n; i++){
            if(a[i] == a[k]){//k名后分数相同的人数
                ans++;
                continue;
            }
        }
        System.out.print(ans);
        input.close();
       }
    }
    
    
    //外部比较器,使sort实现升序
    class  MyCompare implements Comparator<Integer>{
    	@Override
    	public int compare(Integer o1, Integer o2) {
    		return o1 > o2 ? -1 : (o1 == o2 ? 0 : 1);
    	}
    }

### 十、逆序对 ###

\*\*题目：\*\*给你一个长度为n的序列，有m 次操作。每次翻转\[l,r\]的区间，每次操作后询问序列逆序对个数的奇偶性。

/**
    	输入格式:第一行1个正整数，为原序列的长度n ;第二行n个自然数，表示该序列的元素ai ;第三行1个正整数，为操作次数m ;接下来m行，每行两个整数l,r，表示翻转的区间。
    	输出格式:m行，每行表示每次问询的结果。
    
    	样例1   输入: 3
                    1 2 3
                    2
                    1 2
                    2 3
    			输出：odd
    				 even
    	备注   对于30%的分数， 1≤n,m ≤10 ;
    		  对于50%的分数， 1≤n, m ≤100 ;
    		  对于100%的分数，0≤ai≤n,n ≤1500, m ≤200000 。
    */
    #include<bits/stdc++.h> 
    
    using namespace std;
    int n, m, a[1505], q[1505], ans;
    void merge_sort(int l, int r, int a[]){
        if(l >= r){
            return;
        }
        int mid = l + r >> 1;
        merge_sort(l, mid, a);//左有序数组
        merge_sort(mid + 1, r, a);//右有序数组
        int i = l, j = mid + 1, t = 0;
        while(i <= mid && j <= r){
            if(a[i] > a[j]){//左边大，则将右边小的加入临时数组
                q[t++] = a[j++];
                ans += mid - i + 1;
            }else{//否则左边的先加入临时数组
                q[t++] = a[i++];
            }
        }
        while(i <= mid){//只剩下左边
            q[t++] = a[i++];
        }
        while(j <= r){//只剩下右边
            q[t++] = a[j++];
        }
        for(i = l, j = 0; i <= r; i++, j++){
            //a中[l,r]区间内的元素已经有序
            a[i] = q[j];//将排好序的覆盖为原数组
        }
    }
    
    int main( )
    {
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        cin >> m;
        merge_sort(1, n, a);//归并排序
        int l, r;
        while(m--){
            cin >> l >> r;
            //操作后的序列逆序对个数
            ans = ans + (r - l + 1) * (r - l) / 2;
            //判断ans的奇偶性
            cout << (ans % 2 ? "odd" : "even") << endl;
        }
        return 0;
    }

`记录每一个学习瞬间`