长安大学第四届“迎新杯”程序设计竞赛h圣诞节糖果二分

Roni Roni     2022-10-05     316

关键词:

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld

题目描述

圣诞节临近,彩虹岛的黑心商人??????的糖果店又开始热闹了起来,热心的??????来到??????的店里面帮忙包装糖果。店里面共有??堆糖果,其中第??堆有????颗糖果,??????让??????从中选择两堆糖果,这两堆糖果中每?? 颗包装在一起,如果最后还有剩余就归??????所有了,若两堆不足??个则全部归??????所有。作为糖果狂热爱好者,??????当然是想拿走尽量多的糖果,因此他想知道自己最多能够拿走多少糖果。

输入描述:

输入第一行为一个整数??(1 ≤ ?? ≤ 10),表示一共有??组测试数据。
对于每组测试数据:
第一行有两个整数??(2 ≤ ?? ≤ 105), ??(1 ≤ ?? ≤ 109),分别表示糖果堆数和包装后每包糖果的数量。
第二行有??个整数,其中第??个数????(1 ≤ ???? ≤ 109)表示第??堆糖果的数量。

输出描述:

对于每组测试数据,输出一个整数??表示??????能拿走的最多的糖果数目。
示例1

输入

2
4 5
1 4 2 3
4 15
12 19 13 20

输出

4
10

说明

对于第一组样例,??????选择第一堆和第四堆是最佳选择,会剩余4颗糖果。
对于第二组样例,??????选择第一堆和第三堆是最佳选择,会剩余10颗糖果。

【分析】:有个技巧,在输入时就可以%p,再排序,二分查找合法的最大
【代码】:
技术分享图片
#include<stdio.h>
#include<algorithm>
#include <iostream>
#include<string>
#include<math.h>
using namespace std;
int a[100005];
int main()
{
    int n,t,b,c,d,i,max,p,j,low,high;
    cin>>t;
    while(t--)
    {
            cin>>n>>p;
            for(i=0;i<n;i++)
            {
                cin>>a[i];
                a[i]%=p;
            }//每?? 颗包装在一起,
            sort(a,a+n);
            low=0,high=n-1;
            max=(a[n-1]+a[n-2])%p;
            while(low<high)
            {
                while((a[low]+a[high]>=p))//如果两堆糖果中每?? 颗包装在一起,如果最后还有剩余就归??????所有了,
                    high--;
                if(low<high)//两堆不足??个则全部归??????所有
                {
                    if(max<a[low]+a[high]) 
                         max=a[low]+a[high];
                    low++;
                }
            }
            cout<<max<<
;
    }
}
View Code

 

长春理工大学第十四届程序设计竞赛(重现赛)h

H.ArithmeticSequence题目链接:https://ac.nowcoder.com/acm/contest/912/H题目数竞选手小r最喜欢做的题型是数列大题,并且每一道都能得到满分。你可能不相信,但其实他发现了一个结论:只要是数列,无论是给了通项还是给了递推式,无论... 查看详情

hdu6024(中国大学生程序设计竞赛女生专场1002)

这是CCPC女生专场的一道dp题。大佬们都说它简单,我并没有感到它有多简单。先说一下题意:在一条直线上,有n个教室,现在我要在这些教室里从左到右地建设一些作为糖果屋,每个教室都有自己的坐标xi 和建造糖果屋的费... 查看详情

高分!!电子竞赛

...学生电子设计竞赛全国大学生电子设计竞赛广东省大学生程序设计竞赛也称为ACM/ICPC第四届广东省大学生程序设计竞赛(ACM/ICPC广东省赛)第四届广东省大学生程序设计竞赛(ACM/ICPC广东省赛)实施方案The4thGuangdongCollegiateProgramming... 查看详情

湖南中医药大学信息科学与工程学院第四届大学生程序设计竞赛——正式赛题解(代码片段)

目录问题A:X星人的统计问题B:X星人的报数问题C:X星人的迷宫问题D:X星人的高考问题E:X星人的匹配问题F:X星人的成绩问题G:X星人的变换问题H:X星人的游戏问题I:X星人的宝石问题J:X星人的车牌问题K:X星人的括号问题L:X星人的翻译问题... 查看详情

2021年全国行业职业技能竞赛暨第四届全国大学生大数据技能竞赛——职教学生组线上选拔赛(代码片段)

2021年全国行业职业技能竞赛暨第四届全国大学生大数据技能竞赛——职教学生组线上选拔赛目录2021年全国行业职业技能竞赛暨第四届全国大学生大数据技能竞赛——职教学生组线上选拔赛前言资料前提条件题目一、基础配置... 查看详情

第十四届华中科技大学程序设计竞赛决赛同步赛beautifulland(代码片段)

It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.NowHUSTgotabiglandwhosecapacityisCtoplanttrees.Wehaventreeswhichcouldbeplantinit.EachofthetreesmakesHUSTbeautifulwhichdetermine 查看详情

第十四届华中科技大学程序设计竞赛决赛同步赛

第十四届华中科技大学程序设计竞赛决赛同步赛ABeautyofTrees思维,带权并查集题意:长度为n的序列,没告诉你具体数是多少。只给出m个查询,表示区间[l,r]的异或和为k。但是第i个查询如果和前面的查询有矛盾,那就是错误的。... 查看详情

第十四届华中科技大学程序设计竞赛--jvarioustree(代码片段)

链接:https://www.nowcoder.com/acm/contest/106/J来源:牛客网时间限制:C/C++1秒,其他语言2秒空间限制:C/C++32768K,其他语言65536K64bitIOFormat:%lld题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofH 查看详情

浙江财经大学第十四届程序设计竞赛题解

 【题面pdf下载】链接:https://pan.baidu.com/s/1Eb16fHtNYMLrRk9QnXWa-g密码:dwn8【题目牛客网提交链接】【现场赛排名】链接:https://pan.baidu.com/s/1jfzH6-7BoPhEjnijGQK53w密码:y669 感谢各位大佬的参赛。 由于命题人水平不高,而且之前没... 查看详情

第十四届华中科技大学程序设计竞赛cprofessionalmanager并查集删除/虚点(代码片段)

题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.Thusaprofessionaltreemanagerisneeded.Yourtaskistowriteaprogramtohelpmanagethetrees.Initially,therearenforestsandforthei-thf 查看详情

远程幅频特性测试装置(h题本科组)--2017年全国大学生电子设计竞赛试题

...试装置(H题本科组)--2017年全国大学生电子设计竞赛试题一、任务二、要求1.基本要求2.发挥部分三、说明四、评分标准一、任务设计并制作一远程幅频特性测试装置。二、要求1.基本要求(1)制... 查看详情

长春理工大学第十四届程序设计竞赛(重现赛)m.orxzone

链接:https://ac.nowcoder.com/acm/contest/912/M题意:DaenerysStormborn,风暴中出生的丹尼莉丝,theUnburnt,烧不死的,QueenofMeereen,弥林女王,QueenoftheAndalsandtheRhoynarandtheFirstMen,安达尔人,罗伊那人,和先民的女王,LordoftheSevenKingdoms,七国之主 查看详情

第十四届华中科技大学程序设计竞赛jvarioustree数值型一维bfs/最小步数(代码片段)

链接:https://www.nowcoder.com/acm/contest/106/J来源:牛客网题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.AndtherearemanydifferenttypesoftreesinHUST,eachofwhichhasanumberrepresen 查看详情

2017年浙江中医药大学大学生程序设计竞赛(重现赛)h-剪纸

题目描述DDwantstosendagifttohisbestfriendCCasherbirthdayiscoming.However,hecan’taffordexpensivegifts,andheissolazythatheisnotwillingtodocomplexthings.SohedecidestoprepareapapercutforCC’sbirthd 查看详情

北京化工大学2018年10月程序设计竞赛部分题解(a,c,e,h)(代码片段)

目录北京化工大学2018年10月程序设计竞赛部分题解(A,C,E,H)竞赛事件相关竞赛链接竞赛题目总结北京化工大学2018年10月程序设计竞赛部分题解(A,C,E,H)竞赛事件相关竞赛链接虽然我发这个随笔的时候估计已经比完了,不过还是... 查看详情

第十四届华中科技大学程序设计竞赛kwalkingintheforest二分答案/最小化最大值(代码片段)

链接:https://www.nowcoder.com/acm/contest/106/K来源:牛客网题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.Nowyou'regoingtowalkthroughalargeforest.ThereisapathconsistingofNsto 查看详情

用电器分析识别装置(h题)--2021年全国大学生电子设计竞赛

用电器分析识别装置(H题)--2021年全国大学生电子设计竞赛 查看详情

长春理工大学第十四届程序设计竞赛(重现赛)f(代码片段)

F.SuccessionediFixoracci题目链接:https://ac.nowcoder.com/acm/contest/912/F 题目:动态规划(Dynamicprogramming,简称dp)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。例如,假设小x一步能爬1层或2层台阶,求小x爬n... 查看详情