专栏首页Michael阿明学习之路LintCode 1671. 玩游戏(贪心、难)

LintCode 1671. 玩游戏(贪心、难)

1. 题目

N 个人在玩游戏,每局游戏有一个裁判和 N-1 个平民玩家。给出一个数组 A, A[i] 代表玩家 i 至少需要成为平民 A[i] 次,返回最少进行游戏的次数。

样例 1:
输入:A = [2, 2, 2, 2]
输出:3
解析:
A[0] = 2表示玩家0至少需要成为2次平民
第一局:玩家0担任裁判,此时 A[0] = 0, A[1] = 1, A[2] = 1, A[3] =1
第二局:玩家1担任裁判,此时 A[0] = 1, A[1] = 1, A[2] = 2, A[3] = 2
第三局:玩家2担任裁判,此时 A[0] = 2, A[1] = 2, A[2] = 2, A[3] = 3
此时每个玩家都达到了要求,所以进行三局游戏即可

样例 2:
输入:A = [84,53]
输出:137
解析:
第一局:玩家1担任裁判 ,此时 A[0] = 1, A[1] = 0
......
第三十一局:玩家1担任裁判,此时 A[0] = 31, A[1] = 0 
第三十二局:玩家0担任裁判,此时  A[1] = 31, A[1] = 1
第三十三局:玩家1担任裁判,此时  A[1] = 32, A[1] = 1
第三十四局:玩家0担任裁判,此时  A[1] = 32, A[1] = 2
......
第一百三十七局:玩家1担任裁判,此时  A[1] = 84, A[1] = 53
此时每个玩家都达到了要求,所以进行一百三十七局游戏即可

注意事项
∑Ai <= 1e18
1 < n < 1000

2. 解题

  • 直接的想法是,次数最少的那个人当裁判,其他人 -1
  • 然后再排序,重复以上过程,模拟,数据数字非常大,会超时

  • 先排序,除最大的人MAX外,其余人都减去 MAX
  • 前面这 n-1 人的和(一个负数,可以当裁判的次数)
  • 如果这个数的绝对值(当裁判次数)> MAX,那么直接 MAX次游戏结束
  • 否则,裁判次数不够,需要补的次数 / n-1 个人来均摊
class Solution {
public:
    long long playGames(vector<int> &A) {
        // Write your code here
        sort(A.begin(),A.end());
        int n = A.size();
        int MAX = A[n-1];
        long long sum= 0;
        for(int i = 0; i < n-1; ++i)
        {
            A[i] -= MAX;
            sum += A[i];
        }    
        if(sum + MAX <= 0)
            return MAX;
        else
            return ceil((sum+MAX)/double(n-1))+MAX;
    }
};

100% 数据通过测试 总耗时 50 ms 您的提交打败了 54.05% 的提交!

class Solution {	//超时,模拟代码
public:
    long long playGames(vector<int> &A) {
        // Write your code here
        int n =  A.size(), i, c;
        if(n == 2)
            return A[0]+A[1];
        long long sum = 0;
        sort(A.begin(),A.end());
        while(A[0] > 0)
        {
            i= n-2;
            while(i >= 2 && A[n-1] == A[i])
                i--;
            c = A[n-1]-A[i];
            if(c==0)
                c = 1;
            sum += c;
            for(i = n-1; i >= 1; i--)
                A[i] -= c;
            sort(A.begin(),A.end());
        }
        if(A[n-1] > 0)
            sum += A[n-1];
        return sum;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1134. 阿姆斯特朗数

    假设存在一个 k 位数 N,其每一位上的数字的 k 次幂的总和也是 N,那么这个数是阿姆斯特朗数。

    Michael阿明
  • 程序员面试金典 - 面试题 17.23. 最大黑方阵(DP)

    给定一个方阵,其中每个单元(像素)非黑即白。 设计一个算法,找出 4 条边皆为黑色像素的最大子方阵。

    Michael阿明
  • LeetCode 1405. 最长快乐字符串(贪心)

    如果字符串中不含有任何 'aaa','bbb' 或 'ccc' 这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。

    Michael阿明
  • Django的ORM

    调用如下方法会返回查询集 filter all order_by exclude 返回条件之外的数据

    KEVINGUO_CN
  • 顺序表与链表的比较

    结点的数据域a1占8个字节,地址域占4个字节,所以存储密度 = 8 / 12 = 67%

    忆想不到的晖
  • 软件项目开发成本经常用到的估算方法有哪些?

      a、依据工作量估算结果和平均人力成本费率直接计算出直接人力成本和间接成本的总和,加直接非人力成本计算软件开发成本;

    软件成本造价评估
  • Oracle 12c 及以上版本补丁更新说明及下载方法

    Oracle 为了支持与安全相关的修复以及高优先级的非安全修复,将在每年的 1 月,4 月,7 月和 10 月中每个季度发布一个RU。从 2017 年 7 月开...

    JiekeXu之路
  • 动画| 类似Windows的气泡屏保效果

    有时候我们在打印一些CG类型的变量是,无法打印,利用UIKIT中的API可以很方便的实现 字符串和CG变量之间的转换。

    進无尽
  • 数据库中日期的插入(Oracle和Mysql)

    时间静止不是简史
  • flask 项目后台源码安装部署(微信报修小程序源码讲解一)

    这里不详细讲解如何手动安装 flask 及其扩展 , 我针对项目源码使用 PyCharm 开发工具教你如何正确的运行源代码。

    热心的程序员

扫码关注云+社区

领取腾讯云代金券