标题:偶得一题,序列合并求最优解
只看楼主
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
结帖率:100%
已结贴  问题点数:100 回复次数:24 
偶得一题,序列合并求最优解
有若干数字序列,单个数字序列中,不存在重复的数字
需求: 将这些序列合并成一个数字序列, 求合并后的最短序列, 需要保持合并前后序列中数字的前后相对位置不变。

Input:
3
6 5 7 3 2 1 4
3 3 8 5
4 7 5 3 2

Output:
5 7 3 8 5 3 2 1 4

输入说明, 第一行N 表示 总的序列数 范围在[2, 200];接下来的N行,每一行表示一个数字序列, 第一个整数K,表示该序列中数字的个数 范围在[2, 200], 接下来的K个整数为序列中的数字。

输出说明, 序列合并后的 一个最短序列输出



不知道这样描述清楚了没, 如果题没有描述清楚, 请下面跟帖




搜索更多相关主题的帖子: 序列 合并 数字 一个数 表示 
2017-04-29 08:59
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:25 
回复 楼主 寒风中的细雨
题目 D(20 分)
问题描述:
巨人国的小学生放学了,老师要给小朋友们排队了。可是这个老师有强迫症,一定要让路队上的小朋友按身高从高到矮排序。小朋友们呢也很调皮,一旦老师给他排好了队就不愿意动了。这时候小朋友们一个一个从教室里出来了,每个小朋友一出来老师就要给小朋友安排好位置。请问老师最少要给小朋友们排几条路队?

数据输入:
对于每组数据,第一行一个整数 n,表示小朋友的总数(1≤n≤10000)第二行 n 个整数,表示每个小朋友的身高,身高不超过 30000

结果输出:
对于每组数据,输出一个整数,表示最少的路队数

输入示例:
8

389 207 155 300 299 170 158 65

输出示例

2

样例解释:
最少要排两条路队,其中一种方案是:389-207-155-65 和 300-299-170-158


感觉和这题有点像~~~现在没空做题了~先收录到C日记~我猜楼主应该是先自己找到方法再发帖~然后我猜楼主应该会解那一题吧~
收到的鲜花
  • 寒风中的细雨2017-04-29 17:12 送鲜花  5朵   附言:呵呵 这些题都没做。

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-29 11:14
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
这不是拓补排序么~

https://bbs.bccn.net/thread-472197-1-1.html

感觉和这贴的思想有点像~

原来是不存在重复数字啊~那就可以解了~得抽个时间并且在空余时花点时间弄清楚原理才能做~~

[此贴子已经被作者于2017-4-29 15:47编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-29 11:32
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
得分:25 
回复 楼主 寒风中的细雨
正在关注。
那么不同的待合并子序中出现相同的数字要如何处理呢?比如子序列A中5在8之前,子序B中8在5之前?
2017-04-29 14:09
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
得分:0 
回复 4楼 yangfrancis
嗯, 这个是要考虑的
2017-04-29 16:53
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
得分:0 
回复 2楼 九转星河
不一样
2017-04-29 16:56
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
得分:0 
回复 3楼 九转星河
感觉有点像。。。
2017-04-29 17:07
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
得分:0 
还是有点没看懂
Input:
3
6 5 7 3 2 1 4
3 3 8 5
4 7 5 3 2

Output:
5 7 3 8 5 3 2 1 4
这个答案到底咋出来的?
2017-04-29 18:03
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 8楼 yangfrancis
以下是引用yangfrancis在2017-4-29 18:03:35的发言:

还是有点没看懂
Input:
3
6 5 7 3 2 1 4
3 3 8 5
4 7 5 3 2

Output:
5 7 3 8 5 3 2 1 4
这个答案到底咋出来的?


我知道可行的答案是怎么来的~
把每一行的数据代入答案里面会发现答案对于每一行的数据都是按先后次序出现的~~

 5 7 3 2 1 4
在答案里面这些数字从左到右按先后次序出现~其它一样~~问题是要求答案数列元素个数的最小值~



[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-29 18:11
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
得分:25 
下述代码可以得到题主测试数据的结果,没有更多的数据用于测试,也不知道有没有bug:
程序代码:
#include <stdio.h>
void rightmove(int *a,int l)
{//长度为l的数组内数据右移一位,
    for(;l;l--)a[l]=a[l-1];
}
int finddat(int *a,int s,int l,int dat)
{//在长度为l的数组a里查找一个数dat,找到则返回这个数据,没找到则返回-1
    int i,j=-1;
    for(i=s;i<l&&a[i]!=dat;i++);
    if(i<l)j=i;
    return j;
}
void main()
{
    int f,i,j,k,n,s,p,t,a[40001];
    printf("总系列函数(0退出):");
    while(scanf("%d",&n)&&n)
    {
        s=p=0;
        while(n--)
        {
            scanf("%d",&k);
            for(f=1;k;k--)
            {
                scanf("%d",&t);
                i=++p;
                if(f)i=0;
                i=finddat(a,i,s,t);
                if(i<0)
                {
                    if(f)p=s;
                    rightmove(&a[p],s+1-p);
                    a[p]=t;
                    s++;
                }
                else p=i;
                if(f)f=0;
            }
        }
        for(i=0;i<s;i++)printf("%d ",a[i]);
        printf("\n");
        printf("总系列函数(0退出):");
    }
}
2017-04-29 19:33



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-476521-1-1.html




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

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