牛牛寝室有四人,他们打算用一个音响播放自己喜欢的曲子。 但是四人的喜好各不相同,他们每个人选取了自己最喜欢的n首曲子。 也就是一共有4n首曲子,第i首的长度为。 但是他们不能容忍播放别人的曲子的时间比他们长很多,牛牛可以从这些曲子中删掉一些,使得每个人的播放总长大致相等。 牛牛想知道在每个人都至少都播放1首歌的情况下,播放最长时间和播放最短时间的差距最小是多少。-笔试面试资料

这是qklbishe.com第19509 篇笔试面试资料
提供答案分析,通过本文《牛牛寝室有四人,他们打算用一个音响播放自己喜欢的曲子。

但是四人的喜好各不相同,他们每个人选取了自己最喜欢的n首曲子。

也就是一共有4n首曲子,第i首的长度为。

但是他们不能容忍播放别人的曲子的时间比他们长很多,牛牛可以从这些曲子中删掉一些,使得每个人的播放总长大致相等。

牛牛想知道在每个人都至少都播放1首歌的情况下,播放最长时间和播放最短时间的差距最小是多少。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
牛牛寝室有四人,他们打算用一个音响播放自己喜欢的曲子。

但是四人的喜好各不相同,他们每个人选取了自己最喜欢的n首曲子。

也就是一共有4n首曲子,第i首的长度为牛牛寝室有四人,他们打算用一个音响播放自己喜欢的曲子。      但是四人的喜好各不相同,他们每个人选取了自己最喜欢的n首曲子。      也就是一共有4n首曲子,第i首的长度为。      但是他们不能容忍播放别人的曲子的时间比他们长很多,牛牛可以从这些曲子中删掉一些,使得每个人的播放总长大致相等。      牛牛想知道在每个人都至少都播放1首歌的情况下,播放最长时间和播放最短时间的差距最小是多少。

但是他们不能容忍播放别人的曲子的时间比他们长很多,牛牛可以从这些曲子中删掉一些,使得每个人的播放总长大致相等。

牛牛想知道在每个人都至少都播放1首歌的情况下,播放最长时间和播放最短时间的差距最小是多少。

牛牛寝室有四人,他们打算用一个音响播放自己喜欢的曲子。      但是四人的喜好各不相同,他们每个人选取了自己最喜欢的n首曲子。      也就是一共有4n首曲子,第i首的长度为。      但是他们不能容忍播放别人的曲子的时间比他们长很多,牛牛可以从这些曲子中删掉一些,使得每个人的播放总长大致相等。      牛牛想知道在每个人都至少都播放1首歌的情况下,播放最长时间和播放最短时间的差距最小是多少。 寒冰-侠客
DFS+暴力枚举
看题目先看数据。n范围比较小,所以可以dfs出所有的时间可能性。可用用set储存(效率最高),用数组也没关系,可能性不会超过2^10。
然后暴力枚举第k个人的某个时间是最小时间,然后在其他三人中找比这个时间大的最小值。
#include <bits/stdc++.h> typedef long long ll; using namespace std; int n, a[5][15],ans=6000; set<int> t[5]; void dfs(int p,int cur,int sum) {     /**< 指数型枚举所有组合的值,复杂度2^n */     if(cur==n+1)         return;     sum+=a[p][cur];     t[p].insert(sum);/**< 用set存储,用vector也可以,因为数据不超1024 */     dfs(p,cur+1,sum);     sum-=a[p][cur];     dfs(p,cur+1,sum); } int main() {     int i,j,k;     cin>>n;     for(i=1; i<=4; i++)         for(j=1; j<=n; j++)             cin>>a[i][j];     for(i=1; i<=4; i++)         dfs(i,1,0);     set<int>::iterator it;     for(k=1; k<=4; k++) /**< 第k个同学,枚举最小值 */         for(it=t[k].begin(); it!=t[k].end(); it++)         { /**< temp数组初值较大,这样如果最小值枚举失败时计算值会失效 */             int maxv=0,minv=*it,temp[5]={60000,60000,60000,60000,60000};             for(i=1;i<=4;i++)             {                 if(i==k)                     continue;                 if(t[i].lower_bound(minv)!=t[i].end())                    temp[i]=*t[i].lower_bound(minv);                 maxv=max(maxv,abs(minv-temp[i]));             }             ans=min(ans,maxv);          }     cout<<ans;     return 0; } 

今天 10:04:29 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 牛牛寝室有四人,他们打算用一个音响播放自己喜欢的曲子。 但是四人的喜好各不相同,他们每个人选取了自己最喜欢的n首曲子。 也就是一共有4n首曲子,第i首的长度为。 但是他们不能容忍播放别人的曲子的时间比他们长很多,牛牛可以从这些曲子中删掉一些,使得每个人的播放总长大致相等。 牛牛想知道在每个人都至少都播放1首歌的情况下,播放最长时间和播放最短时间的差距最小是多少。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情