问题标题: 酷町堂:奥斯曼打怪兽求满分思路

0
0
已解决
李源徽
李源徽
新手光能
新手光能

考试考完了,蒟蒻460,只有第二题做了60,求满分思路。

题干:

现在有两个奥斯曼打怪兽,他们遇到打不过的怪兽就会发动合体技能,合体技能就是将他们的技能的伤害值相加。现在A奥斯曼和B奥斯曼分别都有n种技能,那么他们就会有n的平方种技能组合,现在求在这n方个中最小的n个伤害技能值是多少。

n<=100000

李源徽在2020-08-05 21:20:19追加了内容

@赵逸凡 @张带数学家

李源徽在2020-08-06 15:01:32追加了内容

@赵逸凡


0
已采纳
赵逸凡
赵逸凡
初级启示者
初级启示者

这道题用优先队列,大根堆,堆顶存放最大元素,然后将每个和值与堆顶比较,如果长度>m则判断是否放入,否则直接放入,但这样写会TLE 90分

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
int n,a[100010],b[100010];
priority_queue<int> q;
priority_queue<int,vector<int>,greater<int> > p;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(q.size()<n)
                q.push(a[i]+b[j]);
            else
            {
                if(a[i]+b[j]>q.top())
                    break;
                else
                {
                    q.pop();
                    q.push(a[i]+b[j]);
                }
            }
        }
    }   
    while(!q.empty())
    {
        p.push(q.top());
        q.pop();
    }
    while(!p.empty())
    {
        printf("%d ",p.top());
        p.pop();
    }
    return 0;
}

还有加写特判优化

0
0
张天璨
张天璨
新手天翼
新手天翼

我100分,我需要题目链接。才能告诉你

0
刘英杰
刘英杰
新手天翼
新手天翼

这题是谁出的

我敲了

奥斯曼?

精罗震怒!!!!!!!!!

 

 

以下是思路

对两组技能的伤害进行排序

然后循环

每次循环时都找出下标和最小的两个技能,若下标和同样小,则找出和最小的技能组合(优化算法)

最后输出满足条件的组合数或者所有组合(根据题目要求而定)

0
王子健
王子健
初级天翼
初级天翼

算法中级班考460还低???

你这题我是不可能会的,你加我QQ:1708262261帮我看一道考试题

0
我要回答