Chinaunix首页 | 论坛 | 博客
  • 博客访问: 342927
  • 博文数量: 122
  • 博客积分: 5000
  • 博客等级: 大校
  • 技术积分: 1191
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-24 11:12
文章分类

全部博文(122)

文章存档

2010年(122)

我的朋友

分类: C/C++

2010-06-04 19:20:15

一、问题描述

 

二、解题思路

首先想到的思路是用五个循环遍历,再加一些剪枝条件,结果半天都没有出结果。遍历应该是行不通的了。

这里用到的思路是将方程分开,即:

-(a1X13+a2X23)=(a3X33+a4X43+a5X53)

首先计算左边的所有可能的结果,并放在一个数组里,然后进行排序。

然后计算左边的结果,同时在数组中查找(二分查找)这个结果是否存在,如果存在,计算出存在多少个。这样需要10000个存储空间,和100万次二分查找。提交结果显示用了1063MS

 

三、代码

 

#include<iostream>
#include<algorithm>
using namespace std;
int d[6][105];
int H[10005];
const int MAX=100;
int len;
int cmp(const void * a,const void * b)
{
    return *(int *)a-*(int *)b;
}
int search_binary(int key,int s,int t)
{
    int m;
    while(s<=t)
    {
        m=(s+t)/2;
        if(H[m]==key)
        {
            int c;
            int d;
            c=d=0;
            int tt=m-1;
            while(tt>=s && H[tt--]==key)
                c++;
            tt=m+1;
            while(tt<=t && H[tt++]==key)
                d++;
            return c+d+1;
        }
        else
        {
            if(H[m]>key)
                t=m-1;
            else
                s=m+1;
        }
    }
    return -1;
}
int main()
{
    int i,j,k,l,m;
    int a[6];
    int temp;
    scanf("%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5]);
    for(i=0;i<50;++i)
    {
        temp=(i-50)*(i-50)*(i-50);
        for(j=1;j<=5;j++)
            d[j][i]=a[j]*temp;
    }
    for(i=51;i<=MAX;++i)
    {
        temp=(i-50)*(i-50)*(i-50);
        for(j=1;j<=5;j++)
            d[j][i-1]=a[j]*temp;
    }
    
    //int L1,L2,L3,L4;

    len=0;
    for(i=0;i<MAX;++i)
    {
        for(j=0;j<MAX;++j)
        {
            H[len++]=(0-(d[1][i]+d[2][j]));
        }
    }
    sort(H,H+len);
    //qsort(H,len,sizeof(H[0]),cmp);//排序

    int sum=0;
    for(k=0;k<MAX;++k)
    {
        for(l=0;l<MAX;++l)
        {
            for(m=0;m<MAX;++m)
            {
                temp=d[3][k]+d[4][l]+d[5][m];
                int times=search_binary(temp,0,len-1);
                if(times!=-1)
                    sum+=times;
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}


阅读(1336) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~