题解 | #一样的水#

一样的水

http://www.nowcoder.com/practice/c880afeeaeeb4316b19e784452216e23

题目:一样的水
描述:有n个水桶,第i个水桶里面水的体积为Ai,你可以用1秒时间向一个桶里添加1体积的水。有q次询问,每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。对于一次询问如果有多种方案,则采用使最终pi个桶中水的体积最小的方案。
示例1:输入:4,3,[1,2,3,4],[2,2,4],返回值:[1,0,5]
说明:第一次:花费一秒变为 2 2 3 4
第二次:已经存在两个水的体积一样的桶
第三次:花费五秒从2 2 3 4变为4 4 4 4

解法一:
思路分析:首先我们分析题目的含义,题目中输入一共包含4个字符,n表示有n个桶,q表示有q次询问,容器a表示n个水桶中初始水的体积,容器p表示需要询问多少次以及询问的值,题目的意思也很明确,就是每询问一次,你需要保证使pi个桶中水的体积相同所花费的最少时间,因为每次1秒钟内只能添加1体积的水。
——我们以示例1为例进行上述分析:
图片说明
——通过对示例1的解析,我们明白了题目的含义,在编写程序的过程中,我们应该首先设定一个存储对象res和对数组a进行升序排序,因为升序排序之后我们可以缩短运行的时间,题目中只要求两个桶的水体积相同,没有要求具体的哪两个桶,其次我们需要遍历询问的对象,因为我们需要通过询问的对象来确定需要几个桶的水的体积相同,所以我们在此需要设定一个指针对象i(i的值为询问数组的首值),我们可以通过i来首先确定一个量,即sum_min,sum_min的值等于第i个值的量乘以i就是有i个桶的水的体积的总量,然后减去前i个数的总和,就可以得到一个初始化的量,随后只需要循环a数组中连续的i个变量进行比对,就能得到一个sum_min的值,通过将数组保存好以后,再开始第二轮循环即可完成所有的值。
实例分析:
图片说明

Python核心代码:

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param n int整型 水桶的个数
# @param q int整型 询问的次数
# @param a int整型一维数组 n个水桶中初始水的体积
# @param p int整型一维数组 每次询问的值
# @return int整型一维数组
#
class Solution:
    def solve(self , n , q , a , p ):
        # write code here
        a.sort()#首先对a进行排序
        res = []#设置存储对象
        for i in p:#遍历询问对象
            start = 0
            sum_i = sum(a[:i])#前i项的和
            dif = sum_i
            sum_min = a[i - 1]*i - sum_i
            #计算得到前方的最小值,就是用该值的大小乘以i减去前面的i项和
            for j in range(i,n):
                dif += a[j] - a[j - i]
                if a[j] * i - dif < sum_min:#验证
                    start = j + 1 - i
                    sum_min = a[j] * i - dif
            a[start:start + i] = [a[start + i - 1]] * i#保存
            res.append(sum_min)#添加进结果中
        return res

——因为我们首先循环的是询问对象组,所以假设询问对象组有N个元素,所以需要遍历N次,因为初始化,不能保证得到的是最小的元素,所以还需要遍历其余连续的i个元素,所以其总的时间复杂度为。因为需要额外的res存储询问返回值的对象,但是结果数组不计入空间复杂度,所以其空间复杂度为

解法二:
思路分析:上述分析,我们清楚的明白了该题目的意思,下面我们还可以首先将原先a数组中的元素做个累加,将累加和返回,然后再根据上述循环进行操作,首先设定一个存储容器的对象res和上述相同,再定义一个sum的值,用来存储和,再根据for循环进行最小值的计算,根据就能得到初始的最小值,和解法一的公式大致相同,最终一直更新位置,然后返回res结果值即可。
图片说明
C++核心代码:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param n int整型 水桶的个数
     * @param q int整型 询问的次数
     * @param a int整型vector n个水桶中初始水的体积
     * @param p int整型vector 每次询问的值
     * @return int整型vector
     */
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {
        // write code here
        int len = a.size();//首先定义a数组的长度
        sort(a.begin(), a.end());//排序
        int sum[10005];//存储前n项和
        sum[0] = 0;
        vector<int> res;
        for(auto i: p){//以询问为循环对象
            int tmp = INT_MAX;
            for(int j = 1; j <= len; j++){//计算累加值
                sum[j] = sum[j-1] + a[j-1];
            }
            int sum_min = 0, ans = INT_MAX, pos;
            for(int j = i; j <= n; j++){//循环判断最小量
                sum_min = a[j - 1] * i - (sum[j] - sum[j - i]);//计算最小值
                if(sum_min < ans){
                    ans = sum_min;//替换
                    pos = j;
                }
            }
            for(int j = pos - 1; j >= pos - i; j--){//将位置进行更新,开始进行新的一轮
                a[j] = a[pos - 1];
            }
            res.push_back(ans);
        }
        return res;
    }
};

——该方法相比于解法一增加了循环的量,需要将数组a的值进行累加,所以时间复杂度为,因为sum数组为存储量固定的数组,所以空间复杂度为

算法自然分析 文章被收录于专栏

在解决问题的同时,不断与人交流学习,通过牛客各式各样的题目,学习分享。

全部评论

相关推荐

感觉这一周太梦幻了,就像一个梦,很不真实~~~感觉这个暑期,我的运气占了99成,实力只有百分之一4.15上午&nbsp;腾讯csig&nbsp;腾讯云部门,面完秒进入复试状态4.16下午&nbsp;美团优选供应链部门,4.18上午发二面4.17晚上&nbsp;阿里国际一面,纯拷打,面完我都玉玉了4.18下午&nbsp;阿里国际二面,是我们leader面的我,很轻松~~4.18晚上&nbsp;约了hr面4.19上午&nbsp;hr面,下午两点口头oc4.19晚上&nbsp;意向书说起来我的暑期好像一次都没挂过~~~~~难道我是天生面试圣体?----------------------------------------------------------------------六个月前,我还是0项目0刷题,当时想的是先把论文发出来再去找实习。结果一次组会,老师打破了我的幻想(不让投B会,只让投刊或者A)我拿头投啊!!!然后就开始物色着找实习,顺便做完了mit的6.s081,但是基本上还是没刷过题目-----------------------------------------------------------------------11月&nbsp;&nbsp;一次偶然的机会,面进了某个耳机厂的手环部门,大概是做嵌入式的,用的是CPP。12月&nbsp;莫名其妙拿到了国创的面试机会,0基础四天速成java基础!居然也给我面过了hhhhh,可能是面试没写题吧入职国创后的几个月,一直没活,天天搁那看剧,都快忘了还有暑期实习这回事了~~~~命运的齿轮在2.26开始转动,因为这一天美团开了,我开始慌了,因为那时的我什么都不会。lc,八股,sql全部是0进度。然后就开始了女娲补天,上班刷题,下班继续做之前的开源,顺便学一学八股。3月到现在,lc也刷到快200了,一天最多提交了47次~~~~~~~~~~八股根据别人的面经总结和博客,写了快十万字的笔记~~~~~~~~~~简历上的实习经历和开源,也努力去深挖了,写了几万字的记录~~~~~~所以面试的时候,基本上都能cover了,面试官问到的基础基本都会,不基础的我就把他往我会的地方引。结果好像还不错,基本上每个面试官评价都挺好的emmmmmmmm
投递阿里巴巴等公司10个岗位
点赞 评论 收藏
转发
点赞 1 评论
分享
正在热议
# 牛客帮帮团来啦!有问必答 #
1151780次浏览 17149人参与
# 通信和硬件还有转码的必要吗 #
11207次浏览 101人参与
# 不去互联网可以去金融科技 #
20417次浏览 256人参与
# 和牛牛一起刷题打卡 #
18994次浏览 1635人参与
# 实习与准备秋招该如何平衡 #
203400次浏览 3627人参与
# 大厂无回复,继续等待还是奔赴小厂 #
4973次浏览 30人参与
# OPPO开奖 #
19206次浏览 267人参与
# 通信硬件薪资爆料 #
265938次浏览 2484人参与
# 国企是理工四大天坑的最好选择吗 #
2227次浏览 34人参与
# 互联网公司评价 #
97701次浏览 1280人参与
# 简历无回复,你会继续海投还是优化再投? #
25037次浏览 354人参与
# 0offer是寒冬太冷还是我太菜 #
454880次浏览 5124人参与
# 国企和大厂硬件兄弟怎么选? #
53909次浏览 1012人参与
# 参加过提前批的机械人,你们还参加秋招么 #
14646次浏览 349人参与
# 硬件人的简历怎么写 #
82288次浏览 852人参与
# 面试被问第一学历差时该怎么回答 #
19398次浏览 213人参与
# 你见过最离谱的招聘要求是什么? #
28119次浏览 248人参与
# 学历对求职的影响 #
161245次浏览 1804人参与
# 你收到了团子的OC了吗 #
538752次浏览 6387人参与
# 你已经投递多少份简历了 #
344243次浏览 4963人参与
# 实习生应该准时下班吗 #
96982次浏览 722人参与
# 听劝,我这个简历该怎么改? #
63525次浏览 622人参与
牛客网
牛客企业服务