| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 872 人关注过本帖
标题:一道拼装模型的题~大家给个思路~谢!
只看楼主 加入收藏
judking
Rank: 2
等 级:论坛游民
帖 子:13
专家分:10
注 册:2010-3-30
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:6 
一道拼装模型的题~大家给个思路~谢!
Dzx从日本回来了,并为TN准备了礼物----一个恐龙模型。TN想把它尽快拼好,但是由于模型很庞大,TN又实在比较懒,所以他希望你为他寻找一个最节省时间的拼装方案。

模型是由N个零件组成的,每次TN可以选取两个零件拼装在一起来组成一个新的零件,直到得到完整的模型。由于零件的复杂程度不同,TN每次拼装所需要的时间也是不同的,对于两个零件A和B,假设他们的复杂程度分别为a和b,则TN要将这两个零件拼装在一起所需要的时间为a+b,而这由两个零件所组成的新零件的复杂程度为a+b。

现在TN已经统计出了每个零件的复杂程度,你能告诉他最快的拼装方发需要多少时间么?

输入
Line 1: N (1 <= N <= 10000),零件数目
Line 2: N Integers,表示每个零件的复杂程度
输出
最快的拼装方案所需要的时间
样例输入
3
1 2 9样例输出
15

这道题谁能给个算法和思路~不胜感激~
   
搜索更多相关主题的帖子: 拼装 思路 模型 
2010-04-12 20:03
hahayezhe
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖南张家界
等 级:贵宾
威 望:24
帖 子:1386
专家分:6999
注 册:2010-3-8
收藏
得分:7 
这是个数字重复利用的问题 就是数字大的用的越少 越快

所以你开始对样式时间进行排序
最小的两个第一次拼装 得到一个新的数
把这个数放到数列里 再排序

每次都用最小的两个拼装 !
2010-04-12 20:53
judking
Rank: 2
等 级:论坛游民
帖 子:13
专家分:10
注 册:2010-3-30
收藏
得分:0 
回复 2楼 hahayezhe
好的谢谢~我待会去试试看~
2010-04-12 22:46
judking
Rank: 2
等 级:论坛游民
帖 子:13
专家分:10
注 册:2010-3-30
收藏
得分:0 
回复 楼主 judking
我编好了~不过在poj(2994)刷的时候超时了````您看看这程序哪里可以优化算法么?我是大一新生~望多指教~
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<memory>
#include<math.h>

int count;

int cmp(const void *aa, const void *bb)    {
    return *(int *)aa - *(int *)bb;
}


void func(int a[], int x, int n)    {
    if(x == n + 1)
        return;
    qsort(a + x - 1, n - x + 2, sizeof(a[0]), cmp);
    count += a[x - 1] + a[x];
    a[x] += a[x - 1];
    func(a, x + 1, n);
    return;
}


int main()    {
    int i, n, a[10010];
    memset(a, 0, sizeof(a));              

    scanf("%d", &n);                      // input
    for(i = 1; i <= n; i ++)    {
        scanf("%d", &a[i]);
    }

    count = 0;
    func(a, 2, n);
    printf("%d\n", count);
    return 0;
}


2010-04-12 23:22
judking
Rank: 2
等 级:论坛游民
帖 子:13
专家分:10
注 册:2010-3-30
收藏
得分:0 
回复 2楼 hahayezhe
我编好了~不过在poj(2994)刷的时候超时了````您看看这程序哪里可以优化算法么?我是大一新生~望多指教~
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<memory>
#include<math.h>

int count;

int cmp(const void *aa, const void *bb)    {
    return *(int *)aa - *(int *)bb;
}


void func(int a[], int x, int n)    {
    if(x == n + 1)
        return;
    qsort(a + x - 1, n - x + 2, sizeof(a[0]), cmp);
    count += a[x - 1] + a[x];
    a[x] += a[x - 1];
    func(a, x + 1, n);
    return;
}


int main()    {
    int i, n, a[10010];
    memset(a, 0, sizeof(a));              

    scanf("%d", &n);                      // input
    for(i = 1; i <= n; i ++)    {
        scanf("%d", &a[i]);
    }

    count = 0;
    func(a, 2, n);
    printf("%d\n", count);
    return 0;
}


2010-04-12 23:24
flyingzc
Rank: 2
等 级:论坛游民
帖 子:22
专家分:13
注 册:2010-4-1
收藏
得分:7 
int cmp(const void *aa, const void *bb)    {
    return *(int *)aa - *(int *)bb;
这个返回的是什么哦 ,解释下啦
2010-04-13 09:08
judking
Rank: 2
等 级:论坛游民
帖 子:13
专家分:10
注 册:2010-3-30
收藏
得分:0 
回复 6楼 flyingzc
就是快排的cmp函数~你去搜下qsort用法就知道了~
2010-04-13 12:32
快速回复:一道拼装模型的题~大家给个思路~谢!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017929 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved