| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5062 人关注过本帖
标题:草狼,你不是很厉害吗, 进来试试
只看楼主 加入收藏
新浪
Rank: 3Rank: 3
来 自:水星
等 级:论坛游侠
威 望:1
帖 子:770
专家分:167
注 册:2008-6-10
收藏
得分:0 
回复 40楼 longlong89
确实是一个闲人, 呵呵。

天下皆醒,唯我独醉;  天下皆白,唯我独黑
2010-08-15 21:32
新浪
Rank: 3Rank: 3
来 自:水星
等 级:论坛游侠
威 望:1
帖 子:770
专家分:167
注 册:2008-6-10
收藏
得分:0 
以下是引用新浪在2010-8-15 16:30:43的发言:

和并查集是完全不同的算法。
这题是一个朋友当时出给我的。被我Ac了.
凭她的个性,估计是搜不到源码的。如果 草狼 能A的出来,我就佩服一下他。
我想体会一下 井底之蛙 的感觉。
得知那人现在在做兼职,忙的都没时间逛论坛。/
我说咋这么长时间不见其踪影呢, 感觉真好 !

[ 本帖最后由 新浪 于 2010-8-15 22:01 编辑 ]

天下皆醒,唯我独醉;  天下皆白,唯我独黑
2010-08-15 21:59
loveoursevle
Rank: 1
等 级:新手上路
帖 子:6
专家分:1
注 册:2010-8-15
收藏
得分:1 
这个…………数学知识要求很强大
2010-08-15 22:00
jack10141
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:陕西西安
等 级:小飞侠
威 望:6
帖 子:706
专家分:2271
注 册:2010-8-10
收藏
得分:0 
回复 41楼 新浪
我换了别的方法,自我感觉应该没问题了!大家帮忙测试下啊。
程序代码:
#include   <stdio.h>
long a[1000][2]={0};
long sum;

long min(long a,long b)
{
    return a<b?a:b;
}
main()
{
    long int  i,j,n,x,y,t;
LOOP:
    printf("请输入纸带数量:(输入0则退出)");
    scanf("%ld",&n);                     /*输入纸带数量*/
    if(n==0)exit(0);
    sum=1;
    printf("请输入纸带起点与终点:");
    for(i=0;i<n;i++)                     /*分别输入n条纸带起点与终点*/
    {
        scanf("%ld %ld",&a[i][0],&a[i][1]);
    }
    for(i=0;i<n;i++)                     /*保证纸带第一点小于第二点    */
        if(a[i][0]>a[i][1])
        {
                t=a[i][0];
                a[i][0]=a[i][1];
                a[i][1]=t;
        }
    for(i=0;i<n-1;i++)                    /*按照起点排序*/
        for(j=n-2;j>=i;j--)
            if(a[j][0]>a[j+1][0])
            {
                t=a[j][0];
                a[j][0]=a[j+1][0];
                a[j+1][0]=t;
                t=a[j][1];
                a[j][1]=a[j+1][1];
                a[j+1][1]=t;
            }
    x=a[0][0],y=a[0][1];                              /*当前图钉所在纸带范围*/
    for(i=1;i<n;i++)
        if(y<a[i][0]) x=a[i][0],y=a[i][1],sum++;  /*纸带不相交情况要增加图钉*/
        else                                          /*纸带相交情况*/
        {
            x=a[i][0];                                  /*当前图钉所在纸带范围为相交部分*/
            y=min(a[i][1],y);
        }
    printf("%ld\n",sum);
    goto LOOP;
}
所有测试数据的结果
程序代码:
请输入纸带数量:(输入0则退出)2
请输入纸带起点与终点:41 467
334 500
1
请输入纸带数量:(输入0则退出)3
请输入纸带起点与终点:169 724
478 962
464 705
1
请输入纸带数量:(输入0则退出)4
请输入纸带起点与终点:145 281
827 961
491 995
942 942
2
请输入纸带数量:(输入0则退出)5
请输入纸带起点与终点:264 648
446 805
890 954
756 840
966 977
4
请输入纸带数量:(输入0则退出)6
请输入纸带起点与终点:306 673
386 745
924 986
290 636
355 767
655 941
2
请输入纸带数量:(输入0则退出)7
请输入纸带起点与终点:724 966
430 457
287 753
383 945
909 946
506 900
591 762
3
请输入纸带数量:(输入0则退出)8
请输入纸带起点与终点:655 836
374 596
21 348
199 668
484 734
53 999
418 938
900 935
4
请输入纸带数量:(输入0则退出)9
请输入纸带起点与终点:451 600
249 519
556 798
303 844
609 989
702 796
798 798
9 157
472 622
4
请输入纸带数量:(输入0则退出)10
请输入纸带起点与终点:538 657
958 998
322 651
21 699
557 892
389 712
600 869
861 932
169 721
189 976
3
请输入纸带数量:(输入0则退出)11
请输入纸带起点与终点:329 368
692 718
753 996
687 866
949 982
481 535
450 466
44 659
292 439
253 510
745 787
6
请输入纸带数量:(输入0则退出)12
请输入纸带起点与终点:905 958
391 625
477 824
334 874
372 833
70 487
297 518
177 773
270 763
668 985
102 480
213 627
2
请输入纸带数量:(输入0则退出)13
请输入纸带起点与终点:802 924
23 972
61 181
3 432
505 593
725 900
187 360
413 974
270 833
711 760
896 926
10 757
170 315
5
请输入纸带数量:(输入0则退出)14
请输入纸带起点与终点:576 758
164 882
86 565
487 577
474 625
627 629
928 962
123 596
737 771
411 547
153 520
790 924
188 763
940 958
5
请输入纸带数量:(输入0则退出)15
请输入纸带起点与终点:578 760
357 477
108 113
887 993
384 405
540 704
835 869
361 896
22 617
112 717
696 932
296 855
53 962
584 734
654 972
5
请输入纸带数量:(输入0则退出)16
请输入纸带起点与终点:457 532
963 993
176 705
962 990
145 353
314 651
740 759
192 605
264 503
829 997
549 556
561 627
467 541
129 240
813 992
824 970
6
请输入纸带数量:(输入0则退出)17
请输入纸带起点与终点:287 847
604 663
706 913
591 704
818 975
539 584
648 971
864 913
75 545
712 769
262 519
985 994
256 652
936 948
282 653
674 923
831 878
7
请输入纸带数量:(输入0则退出)18
请输入纸带起点与终点:259 619
971 971
264 555
815 954
85 710
484 774
380 815
951 977
132 956
689 941
790 885
974 996
152 345
708 712
131 439
958 995
52 269
479 918
5
请输入纸带数量:(输入0则退出)19
请输入纸带起点与终点:866 925
647 807
98 830
292 600
278 799
352 448
882 897
828 851
816 925
658 940
560 655
675 792
361 754
398 714
946 962
161 524
549 923
350 925
910 949
6
请输入纸带数量:(输入0则退出)




[ 本帖最后由 jack10141 于 2010-8-15 23:16 编辑 ]

Coding就像一盒巧克力,你永远不会知道你会遇到什么BUG
别跟我说你是不能的,这让我愤怒,因为这侮辱了你的智慧
2010-08-15 22:35
苗伊
该用户已被删除
收藏
得分:1 
提示: 作者被禁止或删除 内容自动屏蔽
2010-08-15 22:45
mjsxjy
Rank: 2
等 级:论坛游民
帖 子:16
专家分:25
注 册:2008-12-30
收藏
得分:1 
楼上的朋友你没明白楼主题目的意思啊。很好理解嘛。0在什么位置不重要的。反正相对于那些纸带,0的位置都是一定的。所以只需要考虑纸带的下边界和上边界的值。
2010-08-15 23:47
万改称才
Rank: 3Rank: 3
来 自:温州
等 级:论坛游侠
帖 子:58
专家分:113
注 册:2009-11-10
收藏
得分:1 
没有看清楚 题目目的

老师说 : 好好读书
2010-08-16 00:36
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:1 
以下是引用新浪在2010-8-15 16:30:43的发言:

和并查集是完全不同的算法。
这题是一个朋友当时出给我的。被我Ac了.
凭她的个性,估计是搜不到源码的。如果 草狼 能A的出来,我就佩服一下他。
我想体会一下 井底之蛙 的感觉。
这题POJ有,但是题目类型完全不一样。

原题貌似是说一条纸带,要刷成N种颜色(还是怎么着的,忘了),求纸带上面的一系列的点,要求取点位置是被所有颜色刷过的。貌似图论、线段树可解。另外有一种专门处理这个题的方法,我忘了算法名儿了。

专心编程………
飞燕算法初级群:3996098
我的Blog
2010-08-16 02:09
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:1 
这个题不难的
首先可以观察到对于这样两个区间(满足包含关系)
[       ]
  [    ]
只需要覆盖较小的区间即可(忽略大的不影响结果)。
因此先对n个线段进行预处理,并对其按照左端点排序,即形成不多于n个互不包含的区间。
类似下图
[   ]
  [   ]
     [    ]
       [    ]
         [     ]
问题转化为放上最少的点覆盖这些区间。
显然,存在一种最优覆盖,使其所有的点都在区间端点上。这样就可以dp了。
dp方程
设f[i]表示第i个端点放图钉,覆盖i即i之前所有线段的最小端点数
则f[i] = min{f[j]}+1 其中j(j<i)为i端点不能覆盖的端点中离i最近的线段的两个端点以及夹在两个端点间的端点。
再处理下边界就可以了,复杂度为O(n^2)

另外,这个题应该可以贪心,可以将复杂度降得更低。

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2010-08-16 09:18
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
大家有兴趣的话去https://bbs.bccn.net/thread-315491-1-1.html切磋,没必要在这里斗。

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2010-08-16 09:22
快速回复:草狼,你不是很厉害吗, 进来试试
数据加载中...
 
   



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

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