| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6686 人关注过本帖
标题:我做了个题目,但是测试过不了,大家看看
取消只看楼主 加入收藏
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
结帖率:79.37%
收藏
已结贴  问题点数:50 回复次数:19 
我做了个题目,但是测试过不了,大家看看
问题描述:
    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
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
嗯,我估计有可能是要求最优解的算法。还是顺序解法?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-20 20:22
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
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
是不是要么从头开始合并,要么从尾巴开始合并?
如果是这样就简单多了!不知道理解的对不对

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-21 10:27
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
你算一下如果从尾部开始合并是不是测试数据标准答案!

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-21 10:38
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 12楼 jack10141
把你代码的思路给我听听?我不是很理解.

还有怎么选择正确选择堆.将思路给我听听?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-21 15:25
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 10楼 御坂美琴
这样可让别人看的更清楚,嘿嘿

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-21 15:27
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 12楼 jack10141
测试没过:我把详细的测试数据发上来:
输入样例:
299
895 717
766 556
771 668
776 694
947 796
945 174
741 392
974 411
893 59
627 422
991 964
975 484
797 702
506 392
794 391
851 850
761 512
691 50
798 652
932 426
770 666
592 322
774 762
955 143
622 368
652 548
942 941
936 475
738 591
835 608
979 631
812 780
948 910
781 410
630 230
138 127
770 541
467 464
779 760
950 836
903 652
926 906
954 284
264 14
877 568
695 645
897 878
896 800
975 846
678 2
992 648
919 777
618 383
662 314
845 353
931 719
999 995
946 872
557 541
905 351
993 986
894 475
226 119
998 932
790 704
974 966
881 659
215 126
922 915
996 791
515 163
934 761
687 515
939 624
695 623
751 569
623 485
770 605
850 303
993 373
951 941
857 721
392 253
463 454
928 867
828 770
990 355
223 109
654 267
992 977
805 542
683 564
682 374
100 69
996 993
364 309
998 873
608 521
645 404
539 347
568 539
608 353
824 759
839 759
629 434
856 809
989 927
856 791
970 638
910 702
820 405
963 866
998 996
549 97
753 697
767 503
799 594
962 432
982 878
757 657
862 648
506 231
968 963
451 81
907 720
701 106
193 24
816 656
477 242
787 202
857 642
487 237
432 2
391 218
372 17
325 297
733 148
789 516
959 937
997 988
717 679
730 554
684 284
614 579
580 145
534 121
773 148
996 662
964 280
994 917
911 641
625 131
644 106
455 436
987 859
733 416
861 622
576 317
402 359
928 175
874 788
422 385
542 212
974 203
925 770
499 176
650 471
978 578
644 492
554 346
822 755
497 319
855 817
865 830
768 763
595 481
940 932
838 175
426 263
804 780
912 771
772 586
564 275
991 975
833 192
970 789
855 799
524 481
951 524
998 996
903 812
683 404
721 604
639 185
858 830
540 184
869 607
996 995
920 249
616 357
732 602
644 303
983 959
330 274
790 252
233 224
913 910
851 759
878 503
939 919
762 112
600 282
44 22
626 515
637 167
893 633
982 950
820 735
573 471
794 185
990 919
914 475
70 3
887 391
884 859
619 497
622 533
581 280
998 964
687 346
911 629
766 116
990 777
870 774
654 98
858 834
444 223
845 839
489 416
735 650
358 310
709 584
795 793
963 179
664 315
821 632
982 138
806 365
974 890
630 540
982 764
959 770
575 152
699 578
231 5
443 413
895 590
624 242
419 408
623 525
944 919
522 76
937 530
468 381
230 151
860 37
824 375
734 578
732 217
998 995
350 125
758 443
824 242
985 974
832 437
620 313
561 485
920 842
815 529
727 670
683 510
872 857
823 693
223 127
921 873
814 520
819 464
468 138
922 52
893 752
949 817
949 311
753 19
993 295
659 186
907 698
558 428
600 426
959 362
输出样例:
550098


这个能过,基本上就全过了

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-09-21 18:06
快速回复:我做了个题目,但是测试过不了,大家看看
数据加载中...
 
   



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

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