[数据结构与算法]19070 音响外放

?解题思路：做题要训练暴力枚举的能力。能想出暴力的解法就是胜利~~
先看数据。n范围比较小，所以可以用DFS（递归实现指数型枚举）得到每一个人所有的可能得到时间，总数最大不超过1024。
这样用数组分别存储4个人的所有可能时间。此时可以四层循环枚举所有可能，当然这么做必然超时。

发现此题目枚举是有条件可利用，即四个人最大最小差距尽可能小。因此，总会有一个人，他选择的曲子是四个人中最短的。
我们可以先假设第1个人选择的曲子长度X一定是所有人里面最小时间（X最多1024种可能），那么其他人一定比第1个人的值X大，找到其他三个人比X大的最小值，求出差。
然后我们又假设第2个人选择的曲子长度Y一定是所有人里面最小的，参照第一个人处理方法，再来一次。
然后我们又假设第3个人选择的曲子长度Z一定是所有人里面最小的，再来一套处理。
然后我们又假设第4个人选择的曲子长度V一定是所有人里面最小的，再来一套处理。
在上述枚举过程中必然可以找到答案。复杂度为O(2^2n)。

#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;/**< 用set的目的就是能快速二分找到比minv大的最小值，用数组遍历也可以 */
                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;
}