注册 登录
编程论坛 C++教室

各位高手帮我看看这个程序(在学校的网上评测系统做的题),我写的超时了

尹卫 发布于 2010-04-02 21:53, 1104 次点击
/*两个数的和
Time Limit:1000MS  Memory Limit:65536K
Total Submit:22 Accepted:7
Description
给你一组N个整数,你从中找出两个整数并满足这样的条件:它们的和等于SUM。如果存在这样的两个数,就输出YES,否则输出NO。
Input
用while(cin>>).第一行两个整数:N,SUM。
N表示这组整数的个数,SUM表示条件。当输入0 0(即两个0)时程序结束。
第二行N个整数,每个整数用一个空格隔开。(0<=N<=10000000,0<=SUM<=1000000).
Output
一行,表示是否存在这样的两个数。
Sample Input
4 8
1 3 6 4
Sample Output
NO*/
#include<iostream>
using namespace std;
int main(){
    int n,sum,i,j,k;
    while(cin>>n>>sum){
       int a[n],b[n];
       if(n==0&&sum==0)break;
       for(i=0;i<n;i++)
          cin>>a[i];
         int c;
       for(j=0;j<n;j++){
               c=sum-a[i];
            for(k=0;k<n;k++){
                         if(c==a[k]){
                          cout<<"YES";
                              break;}
                            }
                         if(c==a[k]) break;
                                                 }
                   if(c!=a[k])cout<<"NO";   
                     
                 }
       return 0;
    }      
10 回复
#2
尹卫2010-04-02 23:56
各位啊  帮帮忙啊  就是想从算法上改进
我这样的算法太暴力了。
#3
玩出来的代码2010-04-03 00:58
for(j=0;j<n;j++){
               c=sum-a[i];           //这里写错了吧,是a[j]..
            for(k=0;k<n;k++){           //k换成j+1试试时间上怎样。
在一组数中找两个数,就相当与是一个组合的问题,这个题只是在遇到符合的条件就停止了,算法也就这了,在高效的也想不出来,
#4
lucky5635912010-04-03 07:31
是用来做什么?
#5
尹卫2010-04-03 09:38
回复 3楼 玩出来的代码
  把i改了之后交上去还是一样的超时啊!   为什么?
   应该还是算法的问题吧
#6
cnfarer2010-04-03 10:26
回复 楼主 尹卫
不知道你们网上评测系统是怎样一个系统!如何来处理程序或代码运行方式?如果是代码提交的话,那么谁来给你输入数据呢?
#7
壞小子2010-04-03 13:52
c 语言  看不懂了
#8
尹卫2010-04-03 15:47
回复 6楼 cnfarer
就是像北大那样的poj一样 http://acm.pku.,把代码交到评测系统上在进行数据的评测。
#9
书呆2010-04-03 15:57
先排序,比sum大的数直接排除
#10
书呆2010-04-03 16:28
程序代码:
#include <iostream>
#include <algorithm>
using namespace std;

int a[10000000];
int main()
{
    int n,sum,i,j;
    while(cin>>n>>sum)
    {
        if(n==0 && sum==0) break;
        for(i=0;i<n;i++)
            cin>>a[i];
        sort(a, a+n);
        i=0;
        for (j = n-1; a[j] > sum; j--);
        if (j>i)
        {
            while (i!=j)
            {
                if (a[i] + a[j] == sum)
                    break;
                if (a[i] + a[j] > sum) j--;
                else i++;
            }
            if(i==j)
                cout<<"NO"<<endl;
            else
                cout<<"YES"<<endl;
        }  
    }
    return 0;
}   
#11
尹卫2010-04-05 14:42
回复 10楼 书呆
能帮我分析#include <algorithm>吗?  这个东东我不会啊!(初学者啊)
还有程序 sort(a, a+n);和 for (j = n-1; a[j] > sum; j--);
        if (j>i)
        {
            while (i!=j)
            {
                if (a[i] + a[j] == sum)
                    break;
                if (a[i] + a[j] > sum) j--;
                else i++;
            }有些不明白     
请教大虾
         
1