| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6686 人关注过本帖
标题:我做了个题目,但是测试过不了,大家看看
只看楼主 加入收藏
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
结帖率:79.37%
收藏
已结贴  问题点数:50 回复次数:70 
我做了个题目,但是测试过不了,大家看看
问题描述:
    Ztc想把他满屋子的书整理一下,为了应付繁重的学习任务,Ztc已经筋疲力尽了,于是向你求助,请你帮他计算他最少需要花费多少力气。
    书本分成若干堆,呈直线排列。每一堆的书本都有重量W和价值V。Ztc的任务是将所有书本合成一堆。因为Ztc很看重书本的价值。所以他认为合并i,j两堆书本所需要的力气为Wi-Vi+Wj-Vj。合并后的书本的重量和价值均为合并前两堆书的重量和价值的总和。也就是说,合并i,j两堆书后W= Wi+Wj,V=Vi+Vj。
    Ztc不愿意来回走,所以合并只能在相邻的两堆书间进行。书本合并前后,位置不变。如将1,2,3中1,2进行合并,那么合并结果为3,3,再将3,3合并为6(1,2,3,6表示重量)。
   
输入格式
    第1行是1个整数n(2n400)。
    第2..n+1行,每行有2个整数W和V(0<V<W1,000)。
   
输出格式
    仅1行,1个整数f,表示最小力气。
   
样例输入输出:
book.in(这个能过)
3
6 5
9 7
11 2

book.out
15


我的代码:
程序代码:
#include <stdio.h>
#define MAXL 400 //定义最大测资为400
struct book
{
    long int w,v;//每一堆的书本都有重量W和价值V
}book[MAXL];
//公式:合并i,j两堆书本所需要的力气为Wi-Vi+Wj-Vj。
long int strength=0,w_count,v_count=0;//strength为总合并重量,w_count为临时的w和变量,v_count为v和的临时变量
void print()//打印结果
{
    printf("%ld",strength);
}
void sorting_book(int n)
{
    int i;
    for(i=0;i<n-1;i++)//循环n-1次
    {   
     if(i==0)//第一次初始化
     {
     strength=strength+book[i].w-book[i].v+book[i+1].w-book[i+1].v;//将所有book的重量加起来
     w_count=w_count+book[i].w+book[i+1].w;//将w两次的和加起来,第一次初值
     v_count=v_count+book[i].v+book[i+1].v;//将v两次的和加起来,第一次初值
     }
     else
     {
     strength=strength+w_count-v_count+book[i+1].w-book[i+1].v;//相加力气
     w_count=w_count+book[i+1].w;//相加书的重量和价值
     v_count=v_count+book[i+1].v;//相加书的重量和价值
     }
    }
}
main()
{
    int n,i;//n为有几堆书本
    scanf("%d",&n);//输入有几堆书本
    for(i=0;i<n;i++)//输入N堆书
    scanf("%d %d",&book[i].w,&book[i].v);//用户输入数据
    sorting_book(n);//将数据传入sorting_book中   
    print();//打印结果函数
}

再把样例发上来:
样例输入:
10
8 2
98 1
100 54
999 3
2 1
53 9
100 99
77 66
23 22
99 92

输出:
2673

样例输入:
100
1000 1
1000 999
1000 1
768 24
245 9
837 765
349 208
985 34
65 4
230 120
1000 1
1000 1
1000 999
1000 999
99 98
84 75
231 123
954 239
248 111
111 11
356 12
1000 1
1000 1
1000 999
1000 1
1000 353
1000 1
942 1
39 1
23 21
9 12
5 999
999 10
340 203
13 2
874 873
804 710
734 248
249 112
935 24
248 24
358 45
937 27
275 256
57 2
567 56
657 2
869 37
367 267
257 247
457 75
853 57
346 57
87 38
367 38
427 98
194 92
924 53
247 1
1000 99
1000 32
64 21
134 245
235 23
975 42
246 2
463 461
426 75
439 24
429 24
96 2
45 1
349 10
220 44
276 42
256 10
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
样例输出:
244533


数据大一点就过不了,大家帮我看看这个算法有什么问题。谢谢大家!
搜索更多相关主题的帖子: 测试 学习任务 价值 
2010-09-20 18:53
jack10141
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:陕西西安
等 级:小飞侠
威 望:6
帖 子:706
专家分:2271
注 册:2010-8-10
收藏
得分:5 
这个问题关键要解决解题方法!方法走对了,结果才可能正确!!所以,我要慢慢想想看!!!

Coding就像一盒巧克力,你永远不会知道你会遇到什么BUG
别跟我说你是不能的,这让我愤怒,因为这侮辱了你的智慧
2010-09-20 20:11
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
嗯,我估计有可能是要求最优解的算法。还是顺序解法?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-20 20:22
jack10141
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:陕西西安
等 级:小飞侠
威 望:6
帖 子:706
专家分:2271
注 册:2010-8-10
收藏
得分:0 
请你帮他计算他最少需要花费多少力气。

你的代码好像是按照顺序合并书堆!所以肯定不是最优解!!!结果肯定比样例结果大!

PS:有没有输入数据量的要求以及时间空间的限制?

[ 本帖最后由 jack10141 于 2010-9-20 20:42 编辑 ]

Coding就像一盒巧克力,你永远不会知道你会遇到什么BUG
别跟我说你是不能的,这让我愤怒,因为这侮辱了你的智慧
2010-09-20 20:39
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
有:1s,空间为n<400

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-20 20:43
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
如果说要从某一个书堆出发,那么如果是穷举、贪心肯定超时

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-20 20:44
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
如果说n==400,用穷举肯定崩掉

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-20 20:46
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:5 
经典的3次方DP,不过有优化余地,利用一个证明为正确的贪心算法,不过很复杂,网上有解题报告

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-09-20 20:46
jack10141
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:陕西西安
等 级:小飞侠
威 望:6
帖 子:706
专家分:2271
注 册:2010-8-10
收藏
得分:0 
思路其实很简单,我一会在你的基础上,加上我的思路,发出代码你参考下!

Coding就像一盒巧克力,你永远不会知道你会遇到什么BUG
别跟我说你是不能的,这让我愤怒,因为这侮辱了你的智慧
2010-09-20 20:48
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
提醒楼主一句,w和v根本就是可以并起来,没有必要分开计算

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-09-20 20:53
快速回复:我做了个题目,但是测试过不了,大家看看
数据加载中...
 
   



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

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