问题标题: 酷町堂:2010 死神来了 大佬求助

0
0
已解决
栾峻岩
栾峻岩
初级天翼
初级天翼

悲惨命运,只A了#1,#4两个测试点,其他全部TLE……

求优化,O(n²)炸了……

Code:

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=10010;
priority_queue<long long ,vector<long long>,greater<long long> >pq;
int a[MAXN],b[MAXN],c[MAXN],n,m;
int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d %d %d",&a[i],&b[i],&c[i]);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            long long s=j*j*a[i]+j*b[i]+c[i];
            pq.push(s);
        }
    }
    int ans=0;
    while (ans<m)
    {
        printf("%lld ",pq.top());
        pq.pop();
        ans++;
    }
    return 0;
}
//scanf是C语言的输入,在C++中也通用,但需加上头文件:#include <cstdio>

 

求大佬帮忙查错: @陆麟瑞 @黄俊博 @贾敬波  @葛新 @杨喆   @贾文卓 @高翊天 

 

题目:在这 

2010   死神来了

题目描述 Description

死神最近感到压力无比,他要派黑执事去打败虚神界十刃之一牙密.里亚尔戈!死神的黑执事有4个技能(略),但每个技能可能有不止一种威力,所以每招使用完后牙密.里亚尔戈会有n种(分别是F1,F2,F3……Fn)剩余体力(有可能相同)。定义对方剩余体力Fi(x)=Aix^2+Bix+Ci(x∈N*)。现在死神已经知道这些Ai,Bi和Ci以及n,m,请你帮死神(他现在在打虚神界的其他渣渣)求出牙密.里亚尔戈最小的m种剩余体力,死神才能稳操胜券。

输入描述 Input Description

第1行:两个正整数n和m。

第2行~第n+1行:每行三个正整数,其中第i行的三个数分别表示位Ai、Bi和Ci。

输出描述 Output Description

输出为一行:m个数,表示牙密.里亚尔戈所有剩余体力从小到大排序后的前m个,两个数之间有空格

样例输入 Sample Input

 

5 5
4 80 1030
8 90 100
3 50 470
8 80 1000
6 75 6790

样例输出 Sample Output

 

198 312 442 523 582

数据范围及提示 Data Size & Hint

对于10%数据:n,m<=10

对于100%数据:Ai<=10,Bi<=100,Ci<=10 000,n,m<=10 000


0
已采纳
黄俊博
黄俊博
资深光能
资深光能

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sqrt(n)*5;j++)
        {
            heap.push(die[i].a*j*j+die[i].b*j+die[i].c);
        }
    }

黄俊博在2018-12-18 22:10:16追加了内容

@栾峻岩

0
0
0
陈卓
陈卓
修练者
修练者

for(i=0;i<m;i++)

    {

        min1=100000000;

        for(j=0;j<n;j++)

            if(a[j]*f[j]*f[j]+b[j]*f[j]+c[j]<min1)

            {

                min1=a[j]*f[j]*f[j]+b[j]*f[j]+c[j];

                min2=j;

           }

        cout<<a[min2]*f[min2]*f[min2]+b[min2]*f[min2]+c[min2]<<' ';

        f[min2]++;

    }

我要回答