首页 > 试题广场 >

音响外放

[编程题]音响外放

热度指数：80 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

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

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

输入描述:

第一行输入一个整数n，表示每个人都选择了n首曲子。

随后4行，每行n个整数，分别表示第每名室友喜欢的歌曲的时间长度。

对于的数据有

对于的数据有

输出描述:

一行输出一个整数。

示例1

输入

3
240 300 360
600 200 200
300 400 500
600 600 600

输出

说明

分别选用{1,3},{1},{3},{1}时，差距为100。

备注:

算法知识视频讲解

xd_silly

import sys

if __name__ == '__main__':

line = sys.stdin.readline().strip()
song_num = int(line)

songs = []
acc_sums = []
for i in range(4):
line = sys.stdin.readline().strip()
songs.append(list(map(int, line.split(' '))))
sums = []
for j in range(1, 2**song_num):
iter_sum = 0
for k in range(song_num):
if j % 2 == 1:
iter_sum += songs[i][k]
j = j // 2
sums.append(iter_sum)
acc_sums.append(sorted(list(set(sums))))

# print(acc_sums)

sum_set = set()
for i in range(4):
sum_set = sum_set | set(acc_sums[i])

sum_set_list = list(sum_set)
sum_set_list = sorted(sum_set_list)

result = 999999999999
for num in sum_set_list:
song_len_set = [0 for _ in range(4)]
for i in range(4):
for acc_sum in acc_sums[i]:
if acc_sum <= num:
song_len_set[i] = acc_sum
if 0 in song_len_set:
continue
else:
if max(song_len_set) - min(song_len_set) < result:
result = max(song_len_set) - min(song_len_set)
print(result)

发表于 2022-07-14 17:15:00 回复(0)

寒冰-侠客

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;
}

发表于 2021-12-25 10:04:29 回复(0)