[AT ZONe Energy Programming Contest] MAD TEAM
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[AT ZONe Energy Programming Contest] MAD TEAM，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2258字，纯文字阅读大概需要4分钟。
内容图文
前言
这里有一个不太优秀但是很好打的做法。
先说时间复杂度：\(O(15*n^2)\)。如果想看更优时间复杂度，请移步木示木干的博客。
题目
题目大意：
\(N\) 个人，每个人有五个能力值 \(A_i,B_i,C_i,D_i,E_i\)，我们要从中选出三个人成为一个组，一个组中一种能力的能力值定义为所有人该种能力的最大值，一个组的能力值定义为该组五种能力值的最小值。
选出一个组使得其能力值最大并输出之。
\(3\le N \le 3000, 1\le A_i,B_i,C_i,D_i,E_i\le 10^9\)。
讲解
由于有五种能力，三个人，我们考虑谁可以成为这个团队各个能力的顶梁柱，对该能力有贡献，也就是该种能力的最大值。
根据鸽巢原理，至少其中一个人对于该组的贡献至多有一种能力，而其余能力由另外两人贡献。所以我们就直接枚举两个人，再枚举另一个人对改组贡献的能力是哪一种，选择最大的即可。
当然，这样的实现方式有很多，我选择了最好写的排序找最大值。
注意在找最大值的时候不要与前面的人重复了。
代码
考场代码确实比较丑，见谅。
//12252024832524
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 3005;
const LL INF = (1ll << 60);
int n,now;
LL ans;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
struct node
{
LL a[5],ID;
}s[6][MAXN];
bool cmp(node x,node y)
{
return x.a[now] > y.a[now];
}
void update(node A,node B,node C)
{
LL ret = INF;
for(int i = 0;i < 5;++ i)
ret = Min(ret,Max(A.a[i],Max(B.a[i],C.a[i])));
ans = Max(ans,ret);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read();
for(int i = 1;i <= n;++ i)
for(int j = 0;j < 5;++ j)
{
s[0][i].a[j] = Read();
s[0][i].ID = i;
for(int k = 1;k < 6;++ k) s[k][i].a[j] = s[0][i].a[j],s[k][i].ID = i;
}
for(now = 0;now < 5;++ now) sort(s[now]+1,s[now]+n+1,cmp);
for(int i = 1;i <= n;++ i)
for(int j = i+1;j <= n;++ j)
for(int k = 0;k < 5;++ k)
for(int l = 1;l <= 3;++ l)
{
if(s[k][l].ID != i && s[k][l].ID != j)//不要重复了
update(s[5][i],s[5][j],s[k][l]);
}
Put(ans);
return 0;
}
内容总结
以上是互联网集市为您收集整理的[AT ZONe Energy Programming Contest] MAD TEAM全部内容，希望文章能够帮你解决[AT ZONe Energy Programming Contest] MAD TEAM所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。