[ABC270E] Apple Baskets on Circle

[ABC270E] Apple Baskets on Circle

题意

\(n\) 个盘子,每个盘子里有 \(a_i\) 个苹果,有个人在绕盘子,每到一个盘子会吃一个苹果,问当吃到第 \(k\) 个苹果的时候,每个盘子剩下多少个苹果。

思路

二分

二分转了多少轮,但是要记录转完整后还可以多吃几个。

代码

#include <algorithm>
#include <iostream>

using namespace std;

const int MaxN = 1e5 + 10;

long long a[MaxN], n, k, cnt, l, r;

bool Check(long long x) {
  long long cnt = 0;
  for (int i = 1; i <= n; i++) {
    cnt += min(a[i], x);
  }
  for (int i = 1; i < n; i++) {
    cnt += a[i] > x;
  }
  return cnt >= k;
}

int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i], r = max(r, a[i]);
  }
  while (l < r) {
    long long mid = (l + r) >> 1;
    Check(mid) ? r = mid : l = mid + 1;
  }
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += min(l, a[i]), a[i] -= min(l, a[i]);
  }
  for (int i = 1; i < n && sum < k; i++) {
    if (a[i] > 0) {
      a[i]--, sum++;
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << " ";
  }
  return 0;
}

排序

可以转满的圈数肯定是可以用一个盘子里的苹果数加上一个数得成的,所以可以排序然后找这个最大圈数,再进行处理。

代码

#include <algorithm>
#include <iostream>

using namespace std;

const int MaxN = 1e5 + 10;

long long a[MaxN], p[MaxN], n, k, sum, cnt, tmp;

int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i], p[i] = a[i];
  }
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= n; i++) {
    if (sum + (p[i] - p[i - 1]) * (n - i + 1) >= k) {
      cnt += (k - sum) / (n - i + 1), tmp = (k - sum) % (n - i + 1);
      break;
    }
    sum += (p[i] - p[i - 1]) * (n - i + 1), cnt += (p[i] - p[i - 1]);
  }
  for (int i = 1; i <= n; i++) {
    a[i] = max(0ll, a[i] - cnt);
  }
  for (int i = 1; i < n && tmp >= 1; i++) {
    if (a[i] > 0) {
      a[i]--, tmp--;
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << " ";
  }
  return 0;
}

细节

这道题想到思路感觉不是很难,但败就败在了细节上,特别是处理答案和二分的过程。

本文转载于网络 如有侵权请联系删除

相关文章

  • Antd的table筛选,表头columns的filters过滤清空

    大家好,又见面了,我是你们的朋友全栈君。Form+Table实现了自定义筛选菜单的功能。具体可以参考https://ant.design/components/table-cn/#components-table-demo-custom-filter-panel。但是此功能会有bug:选择相应的搜索条件后,点击“搜索”按钮,Table会渲染相应的数据,且Table表头也有自带的过滤功能(实际上是column的filters属性起的作用);然后再点击“清除”按钮,所有的搜索条件和表头里filters过滤的条件都要被清除。但是Table组件表头column里的过滤条件未清空。导致重新发起请求时,table列表展示的仍然是上次带了filters的筛选条件,并没有清空。解决方案:filteredValue。具体API参考:https://2x.ant.design/components/table-cn/具体源码://初始化state:filteredInfoconst[filteredInfo,setFilteredInfo]=useState(null);复制//columns:赋属性fi

  • 优化在 SwiftUI List 中显示大数据集的响应效率

    访问我的博客www.fatbobman.com[1]可以获得更好的阅读体验拥有优秀的交互效果和手感,是很多iOS开发者长久以来坚守的原则。同样一段代码,在不同数据量级下的响应表现可能会有云泥之别。本文将通过一个优化列表视图的案例,展现在SwiftUI中查找问题、解决问题的思路,其中也会对SwiftUI视图的显式标识、@FetchRequest的动态设置、List的运作机制等内容有所涉及。本文的范例需运行在iOS15及以上系统,技术特性也以SwiftUI3.0为基础。首先创建一个假设性的需求:一个可以展示数万条记录的视图从上个视图进入该视图时不应有明显延迟可以一键到达数据的顶部或底部且没有响应延迟响应迟钝的列表视图通常会考虑采用如下的步骤以实现上面的要求:创建数据集通过List展示数据集用ScrollViewReader对List进行包裹给List中的item添加id标识,用于定位通过scrollTo滚动到指定的位置(顶部或底部)下面的代码便是按照此思路来实现的:structContentView:View{ varbody:someView{ NavigationView{ List{

  • 面试篇:两道常见面试sql题

    1.有一个订单表order_tab,字段有:order_id,order_amt,user_id,user_address计算每个用户使用最多的3个地址,以及每个地址使用的次数,对应地址消费的总金额;select user_id, user_address, cnt, order_amt from ( select user_id, user_address, cnt, row_number()over(partitionbyuser_idorderbycntdesc)rn, order_amt from ( select user_id, user_address, count(1)ascnt, sum(order_amt)asorder_amt from order_tab groupby user_id, user_address )t )t1 wherern<=3复制2.最近半年连续7天访问数select count(distinctuser_id) from ( select user_id, row_number()over(partitionbyuser_idord

  • 最新!NLG顶会INLG2021最佳长论文出炉!一作华人学生代表出席今晚INLG

    周杰伦三词作曲,曹植七步成诗。近年来,约束文本生成任务(在特定前提条件下生成自然语言输出)引起越来越多人的兴趣。最新消息,华人学者StevenY.Feng与四位学者JessicaHuynh、ChaitanyaNarisetty、EduardHovy与VarunGangal共同发表的题为“SAPPHIIRE:ApproachesforEnhancedConcept-to-TextGeneration”的研究论文获得了2021年INLG的最佳长论文奖!今晚,论文作者StevenY.Feng将作为代表出席第14届INLG会议,线上分享自然语言生成的团队研究。INLG(InternationalConferenceonNaturalLanguageGeneration)始于1980年代,旨在讨论和传播自然语言生成领域的突破性成果。今年,会议于9月20日至24日在苏格兰阿伯丁举行,与会者会通过虚拟会议介绍他们的研究。除了世界级的研究报告外,今年的会议还包括研讨会、学习教程、受邀专家的讲座和一个讨论小组(讨论题目为“用户希望从NLG的现实应用中获得什么”)。小组讨论由目前在计算机学习、NLG和认知

  • 流媒体服务器平台开发SpringBoot整合WebSocket实现服务器向浏览器主动发送消息的过程方式

    SpringBoot设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置,从而使开发人员不再需要定义样板化的配置。用我的话来理解,就是SpringBoot其实不是什么新的框架,它默认配置了很多框架的使用方式,就像Maven整合了所有的Jar包,SpringBoot整合了所有的框架。本文我们来讲一下在进行流媒体服务器平台EasyNVR开发的时候,使用SpringBoot整合WebSocket实现服务器向浏览器主动发送消息的过程方式。下图代码是主要代码:我们在下图输入框内输入服务器IP地址,成功后服务器会返回连接成功的提示,连接成功后服务器就可以发送消息了。下面是服务器主动向用户发送消息的过程:发送成功后界面也会出现提示。

  • Kubernetes 大规模集群最佳实践

    Kubernetes搭建大规模集群最佳实践Kubernetes自v1.6以来,官方就宣称单集群最大支持5000个节点。不过这只是理论上,在具体实践中从0到5000,还是有很长的路要走,需要见招拆招。官方标准如下:不超过5000个节点不超过150000个pod不超过300000个容器每个节点不超过100个pod内核调优#max-file表示系统级别的能够打开的文件句柄的数量,一般如果遇到文件句柄达到上限时,会碰到 #"Toomanyopenfiles"或者Socket/File:Can’topensomanyfiles等错误 fs.file-max=1000000 #配置arpcache大小 #存在于ARP高速缓存中的最少层数,如果少于这个数,垃圾收集器将不会运行。缺省值是128 net.ipv4.neigh.default.gc_thresh1=1024 #保存在ARP高速缓存中的最多的记录软限制。垃圾收集器在开始收集前,允许记录数超过这个数字5秒。缺省值是512 net.ipv4.neigh.default.gc_thresh2=4096 #保存在ARP高速缓存

  • ABAP在Sublime Text编辑器里语法高亮所必需的两个文件

    ABAP.sublime-completions{ "scope":"source.abp", "completions": [ "ABS", "ACOS", "ADD", "ADD-CORRESPONDING", "ADJACENT", "AFTER", "ALIASES", "ALL", "ANALYZER", "AND", "ANY", "APPEND", "APPENDING", "AS", "ASCENDING", "ASIN", "ASSERT", "ASSIGN", "ASSIGNED", "ASSIGNING", &

  • 线性代数基础

    标量定义一个单独的数表示斜体小写字母:希腊字母:向量定义具有大小(magnitude)和方向的量表示粗体小写字母:粗体希腊字母:箭头表示:元素:分类行向量列向量模范数在一个维线性空间中,若对于任意向量,均有非负实数,并且其满足下列三个条件:(非负性):当且仅当时(齐次性):(三角不等式):则称是向量的向量范数。1-范数2-范数(欧式范数)∞-范数(无穷范数)运算加法数乘点积定义几何定义高维矩阵机器学习基础公式定义二维数组表示大写字母:m×n矩阵A:运算加法对应元素相加基本性质交换率:结合率:乘法的列数与的行数相等矩阵乘法一般不满足交换律转置定义特殊矩阵单位矩阵零矩阵/全0矩阵全1矩阵对角矩阵上三角矩阵下三角矩阵基本性质乘法结合律:乘法左分配律:乘法右分配律:对数乘的结合性:转置线性相关向量空间的一组元素中,若没有向量可用有限个其他向量的线性组合所表示,则称为线性无关或线性独立,反之称为线性相关(linearlydependent)。结论含有零向量的向量组一定线性相关单位向量组线性无关秩向量组的秩一个向量组的秩是的线性无关的向量的个数矩阵的秩如果把一个向量组看成一个矩阵,则向量组的秩就是

  • Android8.0与Android9.0的新特性兼容适配代码修改

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/aqi00/article/details/88759343 《AndroidStudio开发实战从零基础到App上线(第2版)》在书后面的附录中给出了Android8和Android9的主要特性说明,附录表格如下图所示: 不过附录表格只涵盖了常见的功能代码适配,而Android8和Android9的众多新特性还涉及到其它的代码适配,下面就补充列出Android8和Android9的额外兼容处理说明:Android8.01、属性动画组合AnimatorSet增加了setCurrentPlayTime和reverse方法,从而允许倒过来播放属性动画组合。 setCurrentPlayTime和reverse方法的调用方式示例如下:  if(Build.VERSION.SDK_INT>=Build.VERSION_CODES.O){     animSet.setCurrentPlayTime(0);//设置当前播放的时间点     animSet.re

  • 谷歌发布支付新应用 Hands Free:真正的刷脸付款!

    你以为指纹支付很高端?其实从现在来说,就弱爆了。近日,谷歌推出了一款测试性的支付应用HandsFree。有了这款支付应用,用户在指定的商店内付款时,就可以刷脸付款了。这款应用有iOS和Android两个版本,不过需要注意的是,只有达到Android4.2以上以及iPhone4S以上的设备支持。当走进一家餐厅消费,点完东西付账的时候,只需说一句“我要用谷歌来支付”即可,然后收银员将会核对用户之前注册并上传到HandsFree应用的照片,如果一致的话,就会确认并完成交易。不过,这一服务目前只适用于旧金山湾区南部的麦当劳、棒约翰等一些商店。早在去年的5月,谷歌就在I/O开发者大会就提出了这项服务,只是没有把它进一步推广。HandsFree应用主要使用蓝牙、WiFi和位置数据,它可以配套AndroidPay移动支付服务使用,而商户只需要升级当前的刷卡机即可支持AndroidPay。HandsFree项目高级总监帕里·巴特说:“AndroidPay目前已有900万注册用户,但谷歌希望探索,未来的移动支付将会是什么样。”目前,谷歌正在改善确认的方式,打算部署一种店内摄像头系统,它可以通过拍照自动确

  • 【BlackHat专题】Black Hat 2016上,你值得关注的8款安全工具

    哪些渗透测试,逆向工程以及其他安全工具将在BlackHat2016大会上绽放异彩?一起拭目以待吧。2016年7月30日-8月4日,一年一度的美国黑帽大会(BlackHatUSA2016)在拉斯维加斯曼德勒海湾酒店(MandalayBay)顺利举行。除了披露重大安全漏洞外,先进的工具展示过程也是大会必不可少的精彩环节。今年当然也不例外,安全研究人员使出浑身解数,将黑帽大会作为他们思想结晶的展示平台,那么今年究竟有哪些亮眼产品进入大家的视线呢?1.InfectionMonkey展示嘉宾:以色列安全公司GuardiCore的OfriZiv网址:www.infectionmonkey.com简介:受Netflix的ChaosMonkey项目的启发,InfectionMonkey是一个数据中心渗透测试工具,通过启动数据中心中随机散布的部分受感染虚拟机,以测试整个网络安全链中的潜在盲点,帮助安全团队提升数据中心的安全恢复能力。2.ProjectDelta展示嘉宾:韩国科学技术院的ChanghoonYoon&SeungsooLee网址:https://github.com/OpenNetwo

  • Debug的使用方法

    Debug(学完Debug之后要求能够使用Debug查看程序的执行流程)1.1Debug概述Debug:是供程序员使用的程序调试工具,它可以用于查看程序的执行流程,也可也用于追踪程序执行过程来调试程序。1.2Debug操作流程Debug调试,又被称为断点调试,断点其实是一个标记,告诉我们从哪里开始查看。Debug操作流程:如何加断电如何运行加了断点的程序看哪里点哪里如何删除断点1.2.1如何加断点设置要设置断点的代码行,在行号的区域后面单击鼠标左键即可。1.2.2如何运行加了断点的程序1.2.3看哪里看Debug窗口还要看一个Console窗口1.2.4点哪里点Stepinto(F7)这个箭头,也可也直接按F7点Stop结束1.2.5如何删除断点选择要删除的断点,单击鼠标左键即可如果是多个断点,可以每一个再点击依次,也可也全部一次性删除代码中演示:1.4Debug使用练习查看方法调用的执行流程代码演示:Debug执行流程:然后进入方法调用:然后判断为false那么c接收到的值就是30.2然后在控制台就输出了c的值30.2:注意事项:如果过数据来自于键盘录入,一定要记住输入数据,否则就不

  • #数列分块入门 2

    这道题他们说不用分块就用平衡树,所以暴力拆解就用分块。 做了两道分块已经渐渐明白分块的一些模板在这里就放一下吧(用vector比用数组md方便多了) 1void/*修改操作*//*查询操作*/(intl,intr.....,intval)/*修改的要素*/ 2{ 3/*总是先修改(查询)角区间,就是那种不是整块整块的*/ 4for(inti=l;i<=(id[l],n)/*注意结束的区间可能就是l~r所以取min*/;i++) 5{ 6/*暴力枚举修改(查询)*/ 7} 8if(/*l和r不在同一个区间就把r所在的角区间枚举修改(查询)*/) 9{ 10/*暴力~*/ 11/*但是能二分或者别的什么能搞出来,那肯定换一下啦*/ 12} 13/*最后就整块整块的枚举啦*/ 14}复制 这道题就是维护每个块内的元素成单调的,这样最后查询的时候就可以用二分(lower_bound)来进行查询会快很多,而剩下的就只有暴力、暴力再暴力。 1#include<bits/stdc++.h> 2usingnamespacestd; 3intn; 4intblock; 5inti

  • 协程的作用 Python

    1.协程的含义和实现 协程是单进程单线程的超越函数的调度机制,它通过一定的调度手段进行调度。 (Python使用generator机制,greenlet使用汇编控制对程序指向来实现)。 2.协程有什么作用 计算机分为IObound和CPUbound两种类型的task。在这两种情况中,协程都没有什么作用。 为什么? 在CPUboundtask中,cpu被用来执行任务去了。这类task,即使一个一个方法的执行,跟协程的效率还要高出一点点,使用协程没有意义。IOboundtask中,CPU已经陷入系统调用之中,用户空间的调度无论如何也是没有CPU的,这样情况下,协程只能死死的。在这样情况下,祈求高效率,怎么可能。 协程只有在非常有限制的情况下,才有一些用处,在单进程单线程任务中的交互青霞,才有它的用武之地。   3.协程不是未来(反驳赖勇浩)。协程是很早之前就有的。很早之前,windows就有纤程的概念,Linux不太确定。但是它一直作为小众的API而存在。      4.协程的两个评测: importgevent importrandom

  • Android下的挂钩(hook)和代码注入(inject)

    Android是基于linux内核的操作系统,根据语言环境可以简单的划分为java层、nativeC层、linux内核层。java层通过jni与native层交互,使用linux提供的底层函数功能。 因此,类似linux系统,我们可以在Android下实现对另一个进程的挂钩和代码注入。在这简单介绍下挂钩和代码注入的方法和两个库,以及针对《刀塔传奇》实现的代码注入。 利用libinject实现so注入和APIHook 一.so注入 Linux上有一个强大的系统调用ptrace,它提供了父进程观察和控制子进程的能力,并允许父进程检查和替换子进程寄存器的值(大名鼎鼎的gdb也是基于ptrace的),当使用ptrace后,发送给子进程的信号会转发给父进程,而子进程会被阻塞,父进程收到信号后,就可以对子进程进行检查和修改。其原型为: longptrace(enum__ptrace_requestrequest,pid_tpid,void*addr,void*data); 1).enum__ptrace_requestrequest:ptrace要执行的命令。 2).pid_tpid:指示ptr

  • 返回字符串表示的数学表达式的值

      输入一个字符串,返回字符串表示的数学表达式的值。  字符串里面只会包括正整数,+,-两种运算  比如"20+10-5",返回25  备注:没有括号,不考虑溢出   intcal(Stringstr){ if(str==null||str.length()==0){ return0; } char[]charStr=str.toCharArray(); intsum=0; charflag='+'; intcur=0; for(inti=0;i<charStr.length;i++){ cur=0; while(i<charStr.length&&charStr[i]>='0'&&charStr[i]<='9'){ cur*=10; cur+=charStr[i]-'0'; i++; } if(flag=='+'){ sum+=cur; }else{ sum-=cur; } if(i==charStr.length){ break;

  • 正确的使用字符串String

    字符串作为所有编程语言中使用最频繁的一种基础数据类型。如果使用不慎,将会造成不必要的内存开销,为此而付出代价。而要优化此类型,从以下两点入手: 1、尽量少的装箱 2、避免分配额外的内存空间 先从第一点装箱的操作说起,查看如下代码: //发生装箱的代码 StringboxOperate="test"+4.5f;复制 其中间语言IL代码为如下: IL_0000:nop IL_0001:ldstr"test" IL_0006:ldc.r44.5 IL_000b:box[mscorlib]System.Single IL_0010:callstring[mscorlib]System.String::Concat(object,object) IL_0015:stloc.0 IL_0016:callvaluetype[mscorlib]System.ConsoleKeyInfo[mscorlib]System.Console::ReadKey() IL_001b:pop IL_001c:ret复制 不难看出,上述代码发生了装箱的操作(IL代码中的box).装箱之所以会发生性能损耗,因为

  • hubbledotnet 使用笔记

    Hubblevs字符串 <connectionStrings> <addname="Search"connectionString="server=***;uid=Hubble.net;pwd=***;database=***;"providerName="Hubble.SQLClient"/> </connectionStrings> 默认值 Dict.dct178740 查询语句 selecttop10Score,Name,addTimefromWholeSearch_CNwhereNamematch'uac^2^26000^1^1'orderbyScoredesc,addTimedesc 分组查询 GroupBy('Count','ID','TypeID',10)] selectbetween0to9ID,Name,TypeID,SEO_D,TypeName,strURL,addTimefromWholeSearch_CN where (NameContains'uac^5^06000^1^3uac6000^5^0' orNameMatch'u

  • Git

    一、从github上下载项目   切换到存放git版本库的地方                  Gitcloneurl(github上的地址)   二、设置全局用户名   (提交代码的时候就会将用户名和邮箱存入版本库中,其他开发人员就可以看到是谁提交的代码)                gitconfig--globaluser.namegithub上的用户名   三、邮箱   3.1 设置全局的邮箱          gitconfig--globaluser.email邮箱 3.2 查看

  • 阿布云代理ip

    阿布云对爬虫新手比较友好,通过购买之后可以生成通行证书以及通行密钥,可以选取http隧道socks隧道,以及专业版,经典版,动态版进行生成,在接入文档中有你需要选择的ip代理池使用信息,php-python: 我选取了单py和scrapy框架处理的方式: importrequests #要访问的目标页面 targetUrl="http://test.abuyun.com" #代理服务器 proxyHost="http-dyn.abuyun.com" proxyPort="9020" #代理隧道验证信息通行证书以及通行密钥 proxyUser="************" proxyPass="************" proxyMeta="http://%(user)s:%(pass)s@%(host)s:%(port)s"%{ "host":proxyHost, "port":proxyPort, "user":proxyUser, "pass":proxyPass, } proxies={ "http":proxyMeta, "https":proxyMeta, }

  • allegro 16.5带线移动

    edit->move  右侧options中选中ripupetch 然后框选需要移动的元件和线,在被选中的元件和线上单击鼠标,被选中的元件和线就会跟着鼠标移动,在目标位置单击鼠标左键,放下元件和线。 右键done  

相关推荐

推荐阅读