首页 > 试题广场 >

出模拟赛

[编程题]出模拟赛
  • 热度指数:1874 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
有三种难度的题目难度分别为Easy,Medium,Hard。现在你总共有 E+EM+M+MH+H 道题,各个字符串的含义如下:
  1. E表示有E道题目难度为Easy。
  2. EM表示有EM道题目难度可以为Easy或Medium
  3. M表示有M道题目难度为Medium。
  4. MH表示有MH道题目难度可以为Medium或Hard。
  5. H表示有H道题目难度为Hard。
你要用这些题目出尽量多的模拟赛,为了保证题目质量且含有一定的区分度,每场模拟赛需要包含Easy,Medium,Hard 三种难度的题目各一道。求你最多能出多少场模拟赛。

输入描述:
一行五个整数E,EM,M,MH,H。
0 <= E+EM+M+MH+H <= 1018


输出描述:
一行一个数字表示答案
示例1

输入

2 2 1 2 2

输出

3

说明

三组分别是
E + EM + H
E + MH + H
EM + M + MH
应该没有比我更简单的了吧
a,b,c,d,e = map(int,input().split())
print(min(a+b,b+c+d,d+e,(b+c+d+e)//2,(a+b+c+d)//2,(a+b+c+d+e)//3))

发表于 2021-09-15 19:22:24 回复(0)
使用二分搜索来查找模拟赛场数的最大值
def find(i, E, EM, M, MH, H):
    # 容易题不够,从EM中搬
    if E < i:
        # 容易题的剩余数量比场数小
        cur = min(i - E, EM)
        E += cur
        EM -= cur
    # 难题不够,从MH中搬
    if H < i:
        # 难题的剩余数量比场数小
        cur = min(i - H, MH)
        H += cur
        MH -= cur
    # 模拟赛数量还可以往多了办(由于EM和MH分别被搬到E和H了,所以算作中等题)
    if M + EM + MH >= i and E >= i and H >= i:
        # 如果容易题、中等题、难题都够了,那就还可以办更多的比赛
        return True
    return False

if __name__ == "__main__":
    [E, EM, M, MH, H] = list(map(int, input().split()))
    max_val = (E + EM + M + MH + H) // 3     # 每场模拟赛三道题,此时为模拟赛场数的上限
    res = 0
    left, right = 0, max_val
    # 通过二分法来判断能否满足出题要求
    while left <= right:
        mid = (left + right) // 2
        if find(mid, E, EM, M, MH, H):
            left = mid + 1
            res = max(res, mid)
        else:
            # 场数太多,收缩右边界
            right = mid - 1
    print(res)
顺便想吐槽一下这套试卷,怎么一点击第三题就会自动交卷,被坑了好多次,第三题有bug

编辑于 2021-01-17 12:10:22 回复(0)
e,em,m,mh,h=map(int,input().split())
opt=(e+em+m+mh+h)//3 # 一开始用int((e+em+m+mh+h)/3),结果浮点精度爆炸,惨
ae,ah=e+em,h+mh # 先全分配给E和H
 
if m>=opt: # 必补不齐
    print(min(ae,ah,m))
    exit()
 
e2=max(0,min(em,ae-opt)) # E能提供的数目
h2=max(0,min(mh,ah-opt)) # H能提供的数目
print(min(ae-e2,ah-h2,m+e2+h2)) # 补齐后取最少的
是我想简单了还是用例出简单了,我还以为是模拟题,为啥题解们都在二分查找
发表于 2021-03-06 00:18:13 回复(3)
根据题解优化了一下,解决了一些极端情况

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    long long E, EM, M, MH, H;
    cin >> E >> EM >> M >> MH >> H;
    
    long long upper = min({E + EM, EM + M + MH, MH + H});
    long long avg = (E + EM + M + MH + H) / 3;
    auto res = min(upper, avg);
    res = min(res, (E+EM+M+MH) / 2);
    res = min(res, (EM+M+MH+H) / 2);
    cout << res;
    
    return 0;
}


发表于 2022-03-17 14:55:35 回复(1)
O(1)复杂度,列举各种状况即可:
#include <iostream>
using namespace std;

int main() {
    unsigned long long E, EM, M, MH, H, E0, H0, D;
    cin >> E >> EM >> M >> MH >> H;
    // E0是E+EM的和,H0是MH+H的和,即最开始将EM看作E,将MH看作H
    E0 = E + EM;
    H0 = MH + H;
    // 分类讨论
    if (M > E0 || M > H0) {
        // M最高
        cout << min(E0, H0);
    } else if (E0 < H) {
        // E0<H也就是说,可以把所有MH都视为M
        cout << min(E0, M + MH);
    } else if (H0 < E) {
        // 同上
        cout << min(H0, EM + M);
    } else {
        // 看E0和H0哪个更大,将它的上半部分截取加入到M
        // 并且修改E0或H0、EM或MH、M的大小
        if (E0 <= H0) {
            D = H0 - E0;
            H0 -= D;
            MH -= D;
            M += D;
        } else {
            D = E0 - H0;
            E0 -= D;
            EM -= D;
            M += D;
        }
        // 此时E0和H0是等高的
        if (M > E0) {
            // 如果M最高,那么直接输出E0即可
            cout << E0;
        } else {
            // 否则计算需要从E0和H0拿多少填补到M
            // 注意(E0-M)/3是不对的,需要用到ceil除法
            D = (E0 - M + 2) / 3;
            D = min(EM, D);
            D = min(D, MH);
            E0 -= D;
            H0 -= D;
            M = M + 2 * D;
            D = min(E0, M);
            D = min(D, H0);
            cout << D;
        }
    }
}
发表于 2021-03-31 13:37:01 回复(0)
#include<bits/stdc++.h>
using namespace std;
long max(long a,long b)
{
    if(a > b)
        return a;
    else
        return b;
}
int main()
{
    long e,em,m,mh,h;
    cin>>e>>em>>m>>mh>>h;
    long ave = (e + em + m + mh + h)/3;
    long l = e+em,r = mh + h;
    if(m >= ave)
    {
        cout<<min(m,min(l,r));
        return 0;
    }

    long e1 = max(0,min(em,l-ave));
    long h1 = max(0,min(mh,r-ave));
    cout<<min(m + e1+ h1,min(l - e1,r-h1));
    
    
    return 0;
}
发表于 2021-04-01 14:59:05 回复(1)
这题没问题吗,每个题型有多个题,不同的题型不排列组合吗,E+M+H不是吗
编辑于 2022-05-28 21:05:38 回复(0)
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;


int main()
{
    unsigned long long E, EM, M, MH, H;
    cin >> E >> EM >> M >> MH >> H;

    unsigned long long m1 = E + EM;
    unsigned long long m2 = H + MH;
    unsigned long long m3 = EM + M + MH;

    unsigned long long minner = min(m1, m2);
    minner = min(minner, m3);

    cout << min((E + EM + M + MH + H) / 3, minner);

    return 0;
}
发表于 2021-08-28 22:22:09 回复(0)
对出模拟赛数量的范围进行二分查找
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
 
typedef long long int llint;
 
bool judge(vector<llint> T, llint k)
{
    llint t;
    for(int i=0;i<5;i+=2)
    {
        t=T[i]+(i>0?T[i-1]:0);
        if(t<k)
        {
            if(i<4 && T[i+1]+t>=k)
            {
                T[i+1]-=k-t;
            }
            else
                return false;
        }
    }
    return true;
}
 
llint search(vector<llint>& T, llint min, llint max)
{
    if(min==max)
        return min;
    if(min==max-1)
        return judge(T, max)?max:min;
     
    llint mid = min + (max-min)/2;
    if(judge(T, mid))
        return search(T, mid, max);
    else
        return search(T, min, mid-1);
}
 
int main()
{
    vector<llint> T(5);
    llint min,max;
    for(int i=0;i<5;i++)
        cin>>T[i];
    min = T[0];
    max = T[0]+T[1];
    for(int i=1;i<5;i+=2)
    {
        if(T[i]<min)
            min=T[i];
        llint t = T[i] + (i>0?T[i-1]:0) + (i<4?T[i+1]:0);
        if(t>max)
            max=t;
    }
    cout<<search(T,min,max)<<endl;
    return 0;
}


发表于 2021-03-04 10:25:01 回复(0)