文章图片
解题思路：做题要训练暴力枚举的能力。能想出暴力的解法就是胜利~~
先看数据。n范围比较小，所以可以用DFS（递归实现指数型枚举）得到每一个人所有的可能得到时间，总数最大不超过1024。
这样用数组分别存储4个人的所有可能时间。此时可以四层循环枚举所有可能，当然这么做必然超时。
发现此题目枚举是有条件可利用，即四个人最大最小差距尽可能小。因此，总会有一个人，他选择的曲子是四个人中最短的。
我们可以先假设第1个人选择的曲子长度X一定是所有人里面最小时间（X最多1024种可能），那么其他人一定比第1个人的值X大，找到其他三个人比X大的最小值，求出差。
然后我们又假设第2个人选择的曲子长度Y一定是所有人里面最小的，参照第一个人处理方法，再来一次。
然后我们又假设第3个人选择的曲子长度Z一定是所有人里面最小的，再来一套处理。
然后我们又假设第4个人选择的曲子长度V一定是所有人里面最小的，再来一套处理。
在上述枚举过程中必然可以找到答案。复杂度为O(2^2n)。
#include
typedef long long ll;
using namespace std;
int n, a[5][15],ans=6000;
set 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::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< 【栈与队列|19070 音响外放】
推荐阅读
- 算法|Acwing1230. K倍区间
- c++|2022/3/29 每日思维
- 蓝桥杯|蛇形填数【第十一届蓝桥杯B组（C\C++）】
- C语言程序练习|爬动的蠕虫
- 算法笔记练习题|(5.6B)n的阶乘
- 蓝桥杯Java真题|19年蓝桥杯Java B组省赛第三题（数列求值）
- Hbu|2-35 判断回文字符串
- 华师oj|2857. 编辑距离
- 13届蓝桥杯夺奖冲刺营|蓝桥杯省赛夺奖冲刺营贪心算法