首页 > 其他分享 >C. Perform Operations to Maximize Score

C. Perform Operations to Maximize Score

时间:2024-08-20 21:28:01浏览次数:8  
标签:Operations cnt Perform ll 中位数 int ai Score ans

原题链接

题解

着重点:分类讨论+二分中位数

首先,由于要求中位数,我们先将数组进行排序;接着我们取遍所有的ai及其对应中位数。

此时,分歧产生,我们有k次增值的机会,是加到ai(不会改变中位数)上 还是 增值后改变中位数(此时中位数可能改变)?

显然,我们要分类讨论

情况一:我们加到选取的ai上,显然只要bi=1,直接将所有k加给ai即可。

情况二:改变中位数,此时显然我们选择的ai是最大值(贪心);直接求最大中位数不好求,我们将通过二分寻找最大中位数(具体实现看code)。

code

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,k;
struct node{
    ll a;
    int b,id;
    bool operator<(const node &m){
        if (a!=m.a) return a<m.a;
        if (b!=m.b) return b<m.b;
        return id<m.id;
    }
};
node p[N];

bool check(int m){
    int cnt=0,sum=k;
    for (int i=n-1;i>=1;i--){
        if (p[i].a>=m) cnt++;
        else{
            
            if (p[i].b){
                if (sum>=m-p[i].a){
                    sum-=m-p[i].a;
                    cnt++;
                }
                else break;
            }
            
        }
    }
    if (cnt>=n-n/2) return true;
    return false;
}

void solve(int t){
    cin>>n>>k;
    ll MAX=0;
    for (int i=1;i<=n;i++) cin>>p[i].a;
    for (int i=1;i<=n;i++){
        cin>>p[i].b;
        p[i].id=i;
    }
    sort(p+1,p+1+n);
    
    int cnt=n/2;
    ll ans=0;
    if (p[n].b) ans=max(ans,p[n].a+p[cnt].a+ll(k));
    else{
        ll l=p[cnt].a,r=p[cnt].a+k+1;
        while (l+1<r){
            ll mid=(l+r)/2ll;
            if (check(mid)) l=mid;
            else r=mid;
        }
        ans=max(ans,p[n].a+l);
    }
    
    for (int i=1;i<=n;i++){
        if (p[i].b){
            if (i<=cnt) ans=max(ans,p[i].a+k+p[cnt+1].a);
            else ans=max(ans,p[i].a+k+p[cnt].a);
        }
    }
    
    cout<<ans<<endl;
}

int main(){
    //freopen("input.txt","r",stdin);
    int t;
    cin>>t;
    for (int i=1;i<=t;i++){
        solve(i);
    }
    return 0;
}

 

标签:Operations,cnt,Perform,ll,中位数,int,ai,Score,ans
From: https://www.cnblogs.com/purple123/p/18355936

相关文章

  • LeetCode 1383. Maximum Performance of a Team
    原题链接在这里:https://leetcode.com/problems/maximum-performance-of-a-team/description/题目:Youaregiventwointegers n and k andtwointegerarrays speed and efficiency bothoflength n.Thereare n engineersnumberedfrom 1 to n. speed[i] a......
  • 【学习笔记6】论文SQLfuse: Enhancing Text-to-SQL Performance through Comprehensiv
    Abstract        Text-to-SQL转换是一项关键创新,简化了从复杂SQL语句到直观自然语言查询的转换,尤其在SQL在各类岗位中广泛应用的情况下,这一创新显得尤为重要。随着GPT-3.5和GPT-4等大型语言模型(LLMs)的兴起,这一领域得到了极大的推动,提供了更好的自然语言理解......
  • 云原生周刊:Score 成为 CNCF 沙箱项目|2024.08.12
    开源项目推荐KubeOneKubermaticKubeOne自动化管理您所有云环境、本地环境、边缘计算和物联网环境中的集群操作。KubeOne可以安装高可用(HA)的主集群,也可以安装单主集群。MayflyMayfly是一个Kubernetesoperator,使您可以使用基于时间的资源。它会在指定时间创建或删除资源。......
  • OFtutorial04_basicFieldOperations解析
    OFtutorial4.C源码#include"fvCFD.H"//Thisisafunctiondeclaration;thismethodwillcalculatesomescalarvalue//giventhecurrenttime,locationinspacex,andareferencepointx0.The//functionalsoacceptsascalingfactor,scale.......
  • CF1654E Arithmetic Operations 题解
    CF1654E给定一个长度为\(n\)的序列\(a\)。问至少需要修改几个数才能使得\(a\)变为一个等差数列。\(n\leq10^5\),\(1\leqa_i\leq10^5\)。我们可以发现值域\(\leq10^5\)实属可疑,我们可以就这点进行分析考虑对于序列的公差\(d\),如果\(d\)太大的话经过若干......
  • SQL Zoo 7.More JOIN operations
    以下数据均来自SQLZoo1.Listthefilmswherethe yr is1962[Show id, title](列出1962年的电影)SELECTid,titleFROMmovieWHEREyr=19622.Giveyearof'CitizenKane'.(给出《公民凯恩》的年份)selectyrfrommoviewheretitle='CitizenKane'3.List......
  • Ubuntu22.04启动提示Perform MOK management处理方法
    环境查看#lsb_release-aNoLSBmodulesareavailable.DistributorID: UbuntuDescription: Ubuntu22.04.4LTSRelease: 22.04Codename: jammy#uname-aLinuxAiServer6.5.0-45-generic#45~22.04.1-UbuntuSMPPREEMPT_DYNAMICMonJul1516:40:02UTC2x86_64......
  • 2000-2023年上市公司财务困境数据合集(ZScore、RLPM、MertonDD、OScore)(含原始数据+计算
    2000-2023年上市公司财务困境数据合集(ZScore、RLPM、MertonDD、OScore)(含原始数据+计算结果)1、时间:2000-2023年2、来源:上市公司年报3、范围:A股上市公司4、指标:MertonDD模型:证券代码、证券简称、统计截止日期、是否发生ST或*ST或PT、是否发生暂停上市、行业代码、行业名称......
  • VMware Aria Operations 8.18 发布 (新增功能概览) - 多云 IT 运维管理
    VMwareAriaOperations8.18发布(新增功能概览)-多云IT运维管理通过统一的高性能平台,实现跨私有云、混合云和多云环境的IT运维管理。请访问原文链接:https://sysin.org/blog/vmware-aria-operations/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgVMwareAri......
  • Machine Learning Operations
    MachineLearningOperationshttps://ml-ops.org/WithMachineLearningModelOperationalizationManagement(MLOps),wewanttoprovideanend-to-endmachinelearningdevelopmentprocesstodesign,buildandmanagereproducible,testable,andevolvableML-......