每日一题冲刺大厂第十六天 NOIP普及组 三国游戏

简介: 大家好,我是泡泡,给大家带来每日一题的目的是为了更好的练习算法,我们的每日一题为了让大家练到各种各样的题目,熟悉各种题型,一年以后,蜕变成为一个不一样的自己!

今日题目: 三国游戏


题目描述


小涵很喜欢电脑游戏,这些天他正在玩一个叫做《三国》的游戏。


在游戏中,小涵和计算机各执一方,组建各自的军队进行对战。游戏中共有 N 位武将(N为偶数且不小于4),任意两个武将之间有一个“默契值”,表示若此两位武将作为一对组合作战时,该组合的威力有多大。游戏开始前,所有武将都是自由的(称为自由武将,一旦某个自由武将被选中作为某方军队的一员,那么他就不再是自由武将了),换句话说,所谓的自由武将不属于任何一方。


游戏开始,小涵和计算机要从自由武将中挑选武将组成自己的军队,规则如下:小涵先从自由武将中选出一个加入自己的军队,然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将,直到所有的武将被双方均分完。然后,程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武,拥有更高默契值的一对武将组合获胜,表示两军交战,拥有获胜武将组合的一方获胜。


已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合,它采取的具体策略如下:任何时刻,轮到计算机挑选时,它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对,找出所有配对中默契值最高的那对武将组合,并将该组合中的自由武将选入自己的军队。 下面举例说明计算机的选将策略,例如,游戏中一共有66个武将,他们相互之间的默契值如下表所示:


12.png


双方选将过程如下所示:


13.png


小涵想知道,如果计算机在一局游戏中始终坚持上面这个策略,那么自己有没有可能必胜?如果有,在所有可能的胜利结局中,自己那对用于比武的武将组合的默契值最大是多少?


假设整个游戏过程中,对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题,保证对于不同的武将组合,其默契值均不相同。


输入格式


共 N 行。


第一行为一个偶数 N,表示武将的个数。


第 2行到第 N行里,第i+1行有Ni个非负整数,每两个数之间用一个空格隔开,表示i号武将和i+1,i+2,…,N号武将之间的默契值(0≤默契值≤1,000,000,000)。


输出格式


共 1 或 2行。


若对于给定的游戏输入,存在可以让小涵获胜的选将顺序,则输出1,并另起一行输出所有获胜的情况中,小涵最终选出的武将组合的最大默契值。如果不存在可以让小涵获胜的选将顺序,则输出 0。


题目分析


题目难度:⭐️⭐️


题目涉及算法:贪心,排序。


ps:有能力的小伙伴可以尝试优化自己的代码或者一题多解,这样能综合提升自己的算法能力


题解报告:


1.思路


最优解总是每一行(整理后)排名第二大中最大的那个,根据贪心,人去选每行次大元素中最大的一定能选到,此时也能阻止计算机去选更大的元素。同时人不会输。


2.代码


#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[510][510];
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            cin>>a[i][j];
            a[j][i] = a[i][j];
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        sort(a[i]+1,a[i]+1+n);
        if(a[i][n-1]>sum)
        {
            sum = a[i][n-1];
        }
    }
    cout<<"1"<<endl<<sum;
    return 0;
}


目录
相关文章
|
机器学习/深度学习 算法 C++
2019第十届蓝桥杯大赛青少年创意编程省赛C++组试题解析
2019第十届蓝桥杯大赛青少年创意编程省赛C++组试题解析
414 0
|
1月前
|
人工智能 算法 BI
第十四届蓝桥杯省赛大学C组(C/C++)三国游戏
第十四届蓝桥杯省赛大学C组(C/C++)三国游戏
|
5月前
【洛谷 P1046】[NOIP2005 普及组] 陶陶摘苹果 题解(比较)
`NOIP2005普及组`编程题《陶陶摘苹果》:陶陶有10个高度在100-200cm的苹果要摘,手触及最大高度+30cm板凳后能摘到的苹果数。输入10个苹果高度和她的最大触及高度,输出可摘苹果数。样例输入:10个苹果高度和110cm触及高度,输出5,表示能摘5个。代码通过逐个比较苹果高度实现统计。
69 0
|
6月前
|
人工智能 BI 测试技术
三国游戏(第十四届蓝桥杯省赛C++C组)
三国游戏(第十四届蓝桥杯省赛C++C组)
【牛客IOI周赛26-普及组】A-平行四边形
【牛客IOI周赛26-普及组】A-平行四边形
|
6月前
|
人工智能 测试技术 C++
第十五届蓝桥杯模拟赛B组(第二期)C++
第十五届蓝桥杯模拟赛B组(第二期)C++
161 0
第十五届蓝桥杯模拟赛B组(第二期)C++
|
存储 人工智能 测试技术
第十二届蓝桥杯省赛第二场 C/C++ B组 编程题与详解
第十二届蓝桥杯省赛第二场 C/C++ B组 编程题与详解
159 0
|
算法 测试技术 C++
第十一届蓝桥杯第三场软件类省赛 C++ B组 题解(一)
第十一届蓝桥杯第三场软件类省赛 C++ B组 题解
101 0
|
算法 测试技术 C++
第十一届蓝桥杯第三场软件类省赛 C++ B组 题解(二)
第十一届蓝桥杯第三场软件类省赛 C++ B组 题解
151 0
|
人工智能 iOS开发 Windows
(待补充)小蒟蒻的刷题成长之路-------中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛)
(待补充)小蒟蒻的刷题成长之路-------中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛)
136 0