CF 672 div2 D

时间:2022-10-28 23:00:12

http://codeforces.com/contest/672/problem/D

题目大意:

有n个人,每个人有pi的钱,然后可以由如下操作,每次都可以挑选一个最富有的人,把它的钱给最穷的人。但是如果所有的人的钱都相等,那么就不需要执行该操作,该操作最多执行k次。问,贫富之间最大的差值是多少。

思路:

感觉这道题我是以一个奇怪的姿势过了。。。

首先我们sort一下每个人的钱,然后并且统计有几个人的钱数相同。然后再分别从最小的开始加钱和从最大的开始扣钱,这两种每个都计算一次,看看k次操作,以后最小的和最大的人的钱能是多少。

然后可能出现以下的情况

情况1:

右往左扣钱以后的val仍然>=左往右加钱的

如果是大于,那么就是两者之差

如果是等于,如果任意一段的转移的k大于0,那么之间的差值就是1(请仔细想一下)

情况2:

右往左扣钱以后的val<左往右加钱的,如果p的总钱数%n=0,说明能均分,即为0.否则为1.

CF 672 div2 D的更多相关文章

  1. cf 442 div2 F&period; Ann and Books&lpar;莫队算法&rpar;

    cf 442 div2 F. Ann and Books(莫队算法) 题意: \(给出n和k,和a_i,sum_i表示前i个数的和,有q个查询[l,r]\) 每次查询区间\([l,r]内有多少对(i, ...

  2. CF&num;603 Div2

    差不多半年没打cf,还是一样的菜:不过也没什么,当时是激情,现在已是兴趣了,开心就好. A Sweet Problem 思维,公式推一下过了 B PIN Codes 队友字符串取余过了,结果今天早上一 ...

  3. CF R631 div2 1330 E Drazil Likes Heap

    LINK:Drazil Likes Heap 那天打CF的时候 开场A读不懂题 B码了30min才过(当时我怀疑B我写的过于繁琐了. C比B简单多了 随便yy了一个构造发现是对的.D也超级简单 dp了 ...

  4. CF&num;581 &lpar;div2&rpar;题解

    CF#581 题解 A BowWow and the Timetable 如果不是4幂次方直接看位数除以二向上取整,否则再减一 #include<iostream> #include&lt ...

  5. &lbrack;CF&num;286 Div2 D&rsqb;Mr&period; Kitayuta&&num;39&semi;s Technology(结论题)

    题目:http://codeforces.com/contest/505/problem/D 题目大意:就是给你一个n个点的图,然后你要在图中加入尽量少的有向边,满足所有要求(x,y),即从x可以走到 ...

  6. CF 197 DIV2 Xenia and Bit Operations 线段树

    线段树!!1A 代码如下: #include<iostream> #include<cstdio> #define lson i<<1 #define rson i ...

  7. CF&num;345 div2 A&bsol;B&bsol;C题

    A题: 贪心水题,注意1,1这组数据,坑了不少人 #include <iostream> #include <cstring> using namespace std; int ...

  8. CF R303 div2 C&period; Woodcutters

    C. Woodcutters time limit per test 1 second memory limit per test 256 megabytes input standard input ...

  9. CF 192 Div2

    A.Cakeminator 暴搞之,从没有草莓覆盖的行.列遍历 char map[30][30]; int vis[30][30]; int hang[30],lie[30]; int main() ...

随机推荐

  1. 关于js实现分页效果的简单代码

    <!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <title&g ...

  2. List转换成XML

    protected void Button1_Click(object sender, EventArgs e) { var customerlist = CustomerHelper.GetList ...

  3. shell选择语句

    if语句 1) if ... else 语句 if ... else 语句的语法: if [ expression ] then Statement(s) to be executed if expr ...

  4. Think Python - Chapter 11 - Dictionaries

    Dictionaries A dictionary is like a list, but more general. In a list, the indices have to be intege ...

  5. 基于QT开发的第三方库

    基于Qt开发的第三方库 分类: Qt2014-02-12 11:34 1738人阅读 评论(0) 收藏 举报 QT第三方库   目录(?)[+]   文章来源:http://blog.csdn.net ...

  6. 微信的分享功能(针对web手机站页面进行的分享功能)

    把这段js粘贴进,设置可以分享的页面,当微信打开,即可微信进行分享各个圈 $(function(){ var lujing=$("#logimg").attr("src& ...

  7. svn: keywords

    在文件头里面加入下面的关键字: $Date$ $ID$ $Revision$ $Author$ 代码在svn提交时,先选中这几个关键字再提交. Date可能出现中文乱码: 在Control Panel ...

  8. 《Node&period;js In Action》笔记之流程控制

    转向Javascript后,开始学习了node.js,选择的第一本书是<Node.js in Action> 将近一个月时间,断断续续看完,选几个点做下笔记 1.实现串行化流程控制 var ...

  9. 关于图片适配不同尺寸的image View(实战)

    分享人:广州华软 佐罗 一. 前言 在前端开发过程中,设计稿中往往只提供一张图片,但是app内需要用到的尺寸各种各样. 同时图片不仅是信息的直接表达,也会为网站起到美观点缀的作用,图片的变形.过分裁切 ...

  10. linklist和arraylist区别

    ArrayList更适合读取数据,linkedList更多的时候添加或删除数据.