牛牛寝室有四人,他们打算用一个音响播放自己喜欢的曲子。
但是四人的喜好各不相同,他们每个人选取了自己最喜欢的n首曲子。
也就是一共有4n首曲子,第i首的长度为。
但是他们不能容忍播放别人的曲子的时间比他们长很多,牛牛可以从这些曲子中删掉一些,使得每个人的播放总长大致相等。
牛牛想知道在每个人都至少都播放1首歌的情况下,播放最长时间和播放最短时间的差距最小是多少。
第一行输入一个整数n,表示每个人都选择了n首曲子。随后4行,每行n个整数,分别表示第每名室友喜欢的歌曲的时间长度。对于的数据有
对于的数据有
一行输出一个整数。
3 240 300 360 600 200 200 300 400 500 600 600 600
100
分别选用{1,3},{1},{3},{1}时,差距为100。
#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; }