梧桐下的四叶草 2015-01-19 07:39 采纳率: 33.3%
浏览 3328

c++,如何优化程序才不超时?(在线等)

题目描述
沼跃鱼通过你的帮助顺利地打开了宝箱,得到了一把"BILIBILI"电击枪。但是沼跃鱼眉头一皱,发现事情并不单纯——宝箱被拿走后房间入口的那块大石板突然变成了山岭巨人。此时沼跃鱼只好拿着刚到手的电击枪迎战了。沼跃鱼使用了“洞悉”技能看穿了山岭巨人的生命值和电击枪的伤害计算方式。电击枪有四个能量槽,每个能量槽都有n种电力输出大小,若四个能量槽分别选择a1,a2,a3,a4的电力输出大小,则总的伤害为a1+a2+a3+a4。注意,每个能量槽最多只能选一种电力输出大小(不选则伤害为0),而总的能量消耗值与总伤害值相等。现在沼跃鱼想知道是否存在一种搭配方式使得电击造成的伤害刚好等于山岭巨人的生命值而不浪费额外的能量。

输入
输入的第一行是一个整数T(0<T≤20),代表接下来有T组数据。

每组数据的第一行有两个整数n,m(0<n<500, m为非负整数),n代表每个能量槽电力输出大小的种数,m代表山岭巨人的生命值。

接下来4行,每行有n个数代表该能量槽可选的电力输出大小。可选的电力输出大小ai满足0≤ai<10^9。

详情参看样例输入。

输出
每组数据输出一行,若存在至少一种搭配方式使总伤害刚好等于山岭巨人的生命值则输出“YES”,否则输出“NO”(不包含双引号)。

样例输入
2
3 16
3 4 5
2 3 4
4 2 3
4 5 6
1 10
1
2
3
11
样例输出
YES
NO
我的程序如下:

 #include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int t,n,i,j,k,p,flag=0,cg=0;
    long long q,m;
    int a[600],b[600],c[600],d[600];
    cin >> t;
    while (t--)
    {
        cg=0;
        flag=0;
        cin >> n >> m;
        for (i=0;i<n;i++)
        {
            /*cin >> a[i];*/scanf("%d",&a[i]);
            if (a[i]==m)
            {
                cg=1;
            }
        }
        a[n]=0;
        for (i=0;i<n;i++)
        {
            /*cin >> b[i];*/scanf("%d",&b[i]);
            if (b[i]==m)
            {
                cg=1;
            }
        }
        b[n]=0;
        for (i=0;i<n;i++)
        {
            /*cin >> c[i];*/scanf("%d",&c[i]);
            if (c[i]==m)
            {
                cg=1;
            }
        }
        c[n]=0;
        for (i=0;i<n;i++)
        {
            /*cin >> d[i];*/scanf("%d",&d[i]);
            if (d[i]==m)
            {
                cg=1;
            }
        }
        d[n]=0;
        if (cg==1)
        {
            cout << "YES" << endl;
        }
        else
        {
            sort(a,a+n+1);//从小到大排序
            sort(b,b+n+1);
            sort(c,c+n+1);
            sort(d,d+n+1);
            /*for (i=0;i<n+1;i++)
            {
                cout << a[i] << endl;
            }*/
            for (i=0;(i<n+1)&&flag==0;i++)//四重循环枚举,太耗时了
            {
                if (a[i]==a[i+1])
                {
                    continue;
                }
                if (a[i]>m)
                {
                    break;
                }
                for (j=0;(j<n+1)&&flag==0;j++)
                {
                    if (b[i]==b[i+1])
                    {
                        continue;
                    }
                    if (b[i]>m)
                    {
                        break;
                    }
                    for (k=0;(k<n+1)&&flag==0;k++)
                    {
                        if (c[i]==c[i+1])
                        {
                            continue;
                        }
                        if (c[i]>m)
                        {
                            break;
                        }
                        for (p=0;(p<n+1)&&flag==0;p++)
                        {
                            if (d[i]==d[i+1])
                            {
                                continue;
                            }
                            if (d[i]>m)
                            {
                                break;
                            }
                            q=a[i]+b[j]+c[k]+d[p];
                            if (q==m)
                            {
                                cout << "YES" << endl;
                                flag=1;
                            }
                        }
                    }
                }
            }
            if (flag==0)
            {
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}
  • 写回答

1条回答 默认 最新

  • 左少华 2015-01-19 13:20
    关注

    可以尝试一下使用linux内核的动态定时模型!

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题