首页 > 其他分享 >KEYENCE Programming Contest 2024(AtCoder Beginner Contest 374)E题

KEYENCE Programming Contest 2024(AtCoder Beginner Contest 374)E题

时间:2024-10-12 19:49:54浏览次数:7  
标签:二分 AtCoder ft Beginner Contest 题解 ll mid sd

六年级蒟蒻来题解了!!!

题目大意:

给定你一个n,表示有n个生产线,每一个生产线都有两种机器,第i个生产线第一件产品每天可以造Ai件零件但是得付出Pi元的代价,第二件产品每天可以生产Bi件物品但是得付出Qi元的代价,然后给你x元的预算问你所有流水线中的最小值的最大值是多少?

思路:

首先我们想暴力的话肯定是不行的。所以我们只能用二分答案。那二分什么呢?我们看他这个最大值是有单调性的越大它要花的钱也就最大。我们现在就把一个选择性的问题变成了一个判断性的问题。每一次二分到的答案我们尽量的去满足他,算出它所需花的最小数然后在比较看是否符合。判断时的用暴力的思想这一道题就结束了。

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
typedef long long ll;
ll n,x;
vector<pair<pair<ll,ll>,pair<ll,ll>>>v;
ll fun(ll mid){
    ll sum=0;
    for(ll i=1;i<=n;i++){
        ll minn=4e18;
        for(int j=0;j<=v[i].sd.ft;j++){
            minn=min(minn,v[i].ft.sd*j+(max(0ll,mid-j*v[i].ft.ft)+v[i].sd.ft-1)/v[i].sd.ft*v[i].sd.sd);
        }
        for(int j=0;j<=v[i].ft.ft;j++){
            minn=min(minn,v[i].sd.sd*j+(max(0ll,mid-j*v[i].sd.ft)+v[i].ft.ft-1)/v[i].ft.ft*v[i].ft.sd);
        }
        sum+=minn;
        if(sum>x){
            break;
        }
    }
    return sum;
}
//cout
int main(){
    cin>>n>>x;
    v=vector<pair<pair<ll,ll>,pair<ll,ll>>>(n+1);
    for(ll i=0;i<n;i++){
        cin>>v[i+1].ft.ft>>v[i+1].ft.sd>>v[i+1].sd.ft>>v[i+1].sd.sd;
    }
    ll l=0,r=1e9;
    while(l<r){
        ll mid=(r+l+1)/2;
        if(fun(mid)>x){
            r=mid-1;
        }else{
            l=mid;
        }
    }
    cout<<r;
}

如果这篇题解对你有帮助的话,就求求你点一下一个不需钱钱的小小的赞、收藏和关注吧!!求求了! 

标签:二分,AtCoder,ft,Beginner,Contest,题解,ll,mid,sd
From: https://blog.csdn.net/weixin_65585251/article/details/142884343

相关文章

  • 2023 Benelux Algorithm Programming Contest (BAPC 23)
    A-\texttt题意\(n\)个软件包,已知大小,可以同时下载\(k\)个,已经下载好了\(m\)个,选\(k\)个下载使得下载完后进度最大,输出已完成进度所占百分比。思路选最大的\(m+k\)个。代码点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoid......
  • The 2022 ICPC Asia Hangzhou Regional Programming Contest K. Master of Both
    题目链接题意:给定n个字符串,然后给定q种字典序规则,在这q种字典序规则下求出这n个字符串的逆序对数量。思路:我们发现q很大,对于每一种排序规则都遍历一遍n个字符串去求逆序对的数量复杂度太高,所以考虑预处理。我们知道要判断两个字符串字典序的大小关系,只需要知道它们第......
  • AtCoder Beginner Contest 373 (A-F)
    AtCoderBeginnerContest373(A-F)比赛链接A-September#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidShowball(){intans=0;for(inti=1;i<=12;i++){strings;cin>>s;ans+=((int)s.si......
  • The 2021 ICPC Asia Shenyang Regional Contest
    目录写在前面E签到F签到JBFSB带权并查集H图论I数学L树形DP,容斥M字符串,离线,单调性G贪心写在最后写在前面比赛地址:https://codeforces.com/gym/103427。以下按个人向难度排序。唉唉国庆vp三场唯一打的还像人的一场,最后手里还有两道题在写可惜都没出来呃呃。被树上背......
  • 【做题笔记】Atcoder 之 dp 专题训练
    ABCDEFGHI概率dp。设\(dp_{i,j}\)表示前\(i\)个硬币中有\(j\)个正面的概率。转移显然:\(dp_{i,j}=dp_{i-1,j-1}\timesp_i+dp_{i-1,j}\times(1-p_i)\)当\(j=0\)时,前\(i\)个硬币中没有正面。所以只能由反面的概率转移过来,转移为:\(dp_{i,j}=dp_{i-1,j}\time......
  • The 2023 ICPC Asia Hangzhou Regional Contest (The 2nd Universal Cup. Stage 22: H
    The2023ICPCAsiaHangzhouRegionalContest(The2ndUniversalCup.Stage22:Hangzhou)M.V-Diagram题意:给定一个“v图”,求平均值最大的子"v图"思路:原图的最低点以及左右两个点必须取,如何先取满左边或者右边在贪心即可voidsolve(){lln;cin>>n;vect......
  • AtCoder Beginner Contest 374(D-E)
    A-C:惯例是宝宝题,会打暴力就能过哈D:其实也是暴力dfs,有一个double打错成int(我是猪鼻),卡了我很久#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e3+10,eps=1e-7;intn,s,t;boolvis[10];doublesum=1e8;structNode{ doublex,y,x1,y1;}a[maxn];doub......
  • キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374)
    A.Takahashisan2判断一个字符串是否以san结尾usingnamespacereader;intmain(){strings;cin>>s;if(s[s.length()-1]=='n'ands[s.length()-2]=='a'ands[s.length()-3]=='s'){cout<<"Yes";......
  • AtCoder Beginner Contest 355
    ABC355A-WhoAtetheCake?题目传送门代码(签到题)#include<cstdio>#include<cctype>#include<cstring>#include<algorithm>usingnamespacestd;intiut(){intans=0,f=1;charc=getchar();while(!isdigit(c))f=(c=='-'......
  • AtCoder Beginner Contest 373
    ABC373A-September题目传送门代码(签到题)#include<cstdio>#include<cstring>usingnamespacestd;chars[1111];intans;intmain(){for(inti=1;i<=12;++i){scanf("%s",s+1);if(strlen(s+1)==i)++ans;}pr......