要不你再看看？ 能不能说说你的思路？

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

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
6
Press any key to continue
我手工验证下看看

谁能写个测试数据，免得一个个对，麻烦死了

不好意思， 随机生成了 18组 小数据， 没测出异常，
3
1 7
4 9
4 8
3
8 9
5 7
6 8
3
9 10
5 8
7 9
3
7 9
3 9
8 10
3
6 8
6 9
0 2
3
6 8
9 12
6 7
3
8 9
2 9
1 3
3
5 9
8 9
7 10
3
2 6
0 1
6 7
3
5 6
0 7
1 7
3
7 8
7 9
9 11
3
4 7
8 9
9 12
3
8 9
0 8
7 9
3
8 10
3 7
1 7
3
3 4
9 11
9 13
3
9 10
8 9
7 8
3
2 8
9 12
2 4
3
6 8
2 9
7 9

我知道我的思路问题出在哪里了，呵呵 是有问题，好像方法不对头，有特例会使算法失效。
新的改进算法正在考虑……

原本的算法就是两两取交集，然后删除一个，保留交集，没有交集则全保留。。。。。。。。。。但是有特例使算法失效

这个问题 最笨的办法就是穷举法，然后找最优解！只是在寻找有没有别的简单办法而已！

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

我前面的程序，我给这组数据，肯定算法失效：
4
1 10
8 12
11 13
1 3
我前面的程序给出结果：
3
但是 只要2个图钉就好

改一下也是一样的

你再试试？？还对么？？

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

1 1 这样的纸带就不用考虑了， 不存在这样的0长度纸带

哥呀，3 是对的。

#include "stdio.h"
#include "malloc.h"

typedef struct Zhidai{
    int q;
    int z;
}Z;

int fun(Z *a,int m);

int main()
{
IP:    int m;
    scanf("%d",&m);
    Z *a;
    a=(Z *)malloc(m*sizeof(Z));
    for(int i=0;i<m;i++)
        scanf("%d %d",&((a+i)->q),&((a+i)->z));
    printf("%d\n",fun(a,m));
    goto IP;
    return 0;
}

int fun(Z *a,int m)
{
    int p=0;
    int sum=1;
    for(int i=0;i<m;i++)
        {
            if((a+p)->z>(a+i)->z)
                p=i;
        }
    while(1)
    {
        int x=-1;
        bool b=true;
        for(int j=0;j<m;j++)
        {
            if((a+j)->q>(a+p)->z)
            {
                if(b)
                {
                    x=j;
                    b=false;
                }
                if((a+x)->q>=(a+j)->q)
                    x=j;
            }
        }
        if(x!=p && x>=0)
        {
            sum++;
            p=x;
        }
        else
            break;
    }
    return sum;
}

新手，刚写的一个，希望大家改正····方法是贪心算法里面的活动安排问题

闲的蛋疼吧 围观