• 奇虎360 一道笔试题 分享一下

    2015/09/22 王先生 35 评论

绘画展览门票每张5元,如果有2*n个人排队购票,每人一张,并且其中一半人恰有5元钱,另一半人恰有10元钱,而票房无领取可找,那么如何将这2*n个人排成一列,顺次购票,使得不至于因票房无零钱可找而耽误时间,应该采用什么算法解决呢?

2 1 收藏


直接登录
最新评论
  • 93吸血鬼 学生 2015/09/22

    一个5元一个10元咯

  • 有五块的在前,十块的在后不就ok了?if i >5 i滚蛋。

  • h2o 找工作中~,求打包 2015/09/22

    import java.util.Scanner;

    public class Main {
    static int n; // n个人
    static int[] a; // 购票队伍
    static int mmTake5; // 售票mm手中5元
    static int take5; // 手拿5元的人的个数
    static int take10; // 手拿10元的人的个数
    static int count; // 满足要求的排队方案的个数

    public static void dfs(int i) {
    if (i == 2 * n) { // 排满了队
    for (int temp : a) {
    System.out.print(temp + ” “);
    }
    System.out.println();
    count++;
    } else { // 未满就继续排啊
    // 不是5元就是10元 new int[] { 5, 10 }
    for (int temp : new int[] { 5, 10 }) {
    switch (temp) {

    // 5元的人
    case 5:
    if (take5 > 0) {
    take5–;// 拿5元的人少了1个
    mmTake5++; // mm手中就多了一张5元
    a[i] = 5; // 5元的人排队
    dfs(i + 1); // 下面的人请保持队型
    mmTake5–; // 还原
    take5++;
    }
    break;

    // 手拿10元
    case 10:
    if (take10 > 0) {
    // 如果手中的5元数大于0,说明可以找5元给拿10元买票的人,就可排队
    if (mmTake5 > 0) {
    take10–;// 拿10元的少了1人
    mmTake5–; // 售票mm手中少了1张5元
    a[i] = 10; // 10元的人排队
    dfs(i + 1); // 下面的人请保持队型
    mmTake5++; // 还原
    take10++;
    }
    }
    break;
    default:
    break;
    }
    }
    }
    }

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(“请输入 n:”);
    if (sc.hasNextInt()) {
    n = sc.nextInt();
    a = new int[2 * n];
    count = 0;
    mmTake5 = 0;
    take5 = n;
    take10 = n;
    dfs(0); // 从0号位开始排队
    System.out.println(“满足的队列的方案数:” + count);
    }
    sc.close();
    }
    }

  • Spark爱好者   2015/09/23

    题目关键点,保证数组n[5,5,5,10,10,10] 排在前面的5元的人> or == 排在前面的10元的人

    n = [5,5,5,5,5,5,10,10,10,10,10,10]

    def func(n):
    len_n = len(n)
    count_10 = 0
    count_5 = 0
    for i in xrange(0, len_n):
    if n[i] == 5:
    count_5 += 1
    else:
    count_10 +=1
    if count_10 > count_5:
    print(i)
    print(n[i+1:])
    index_5 = n[i+1:].index(5)
    n[i],n[index_5+1+i] = n[index_5+1+i],n[i]
    count_10 -= 1
    count_5 += 1
    return n

    print(func(n))

  • 嘿嘿   2015/09/23

    5块钱的排前面10块钱的统统去后面等

  • andres 程序员 2015/09/23

    struct Person {
    char money;
    };

    char visitor[2*n] = {…};
    char temp;
    int i = 0;
    int j = 1;
    while (j != 2*n+1 && i != 2*n) {
    if (visitor[i].money == 5) {
    i += 2;
    continue;
    }
    temp = visitor[i];
    visitor[i] = visitor[j];
    visitor[j] = temp;
    j += 2;
    }

  • andres 程序员 2015/09/23

    只用保证5块的排在奇数位就OK了

  • Clark Li 软件工程师 2015/09/23

    波特兰数

  • 组合数学中的卡特兰数

  • 难道不是用判断吗

  • 把5块看成入栈操作,10块看成出栈操作,问怎么排出一个合法序列。卡特兰数是计算有多少个序列吗?那怎么排呢?

  • wangbiaoo 开发工程师 2015/09/23

    def get_first_seq(n):
    people_5 = [5 for i in range(n / 2)]
    people_10= [10 for i in range(n/2)]
    print people_5,people_10
    people_10.extend(people_5)
    return people_10

    def get_one_ok_seq(n):
    first_seq = get_first_seq(n)
    print first_seq
    count_5 = 0;
    best_seq = []
    for i, data in enumerate( first_seq):
    if data == 5:
    count_5 += 1
    if data == 10:
    count_5 -= 1
    if count_5 < 0:
    print 'count_5 < 0', count_5, first_seq
    next_5_index = first_seq[i:].index(5)
    first_seq[i+next_5_index] = 10
    first_seq[i] = 5
    count_5 += 2
    best_seq.append( first_seq[i])
    return best_seq
    print get_one_ok_seq(10)

  • 小虫py   2015/09/23

    这个排队一点没有操作性

  • 小C   2015/09/23

    其实我有一个问题:是要遍历次数最小呢,还是位置调整次数最少呢?不然的话,方法一大坨。。。。。

  • 笨小孩   2015/09/23

    让有五块的n人 把钱给有十块的n人 分别对应 一人给一个
    然后十块的的n人买两张票 把多的一张给那个给他五块的那人
    这只是最快的 但是如果每人一张的话 就只能五块 十块 穿插买票

  • 遍历数组前1/2,
    5的位置放入结果数组前端,10的位置放入结果数组后端。剩下的原顺序填入结果数组空余。

    对于前n人,假设有m个5元、n-m个10元;则剩余后半部分至多m个10元,故不会出现无零钱可找的情况。

  • 宵伯特 学生 2015/09/24

    N个10 之前至少有N个5即可。
    优先排拿着5块钱的,并计数+1,
    排10块钱的时候,计数-1,
    如果遇到10块钱的,且当前的计数等于0,那么就让个人进入等候队列。
    排下一个的时候,检查等候队列,如果有人,且当前计数不为0,那么久排入队列中,通常也是10块钱的,计数减一即可。
    重复以上步骤,直到排完,如果最后等候队列有人,且计数为0,那么那几个人就甭想近去了。
    这样排的话,人的活动量不大,但是,需要全部遍历一遍。

  • Cmder Cmder 2015/09/25

    只要保证前面有5元钱的人比10元钱的人多就行,也就是卡特兰数的应用!没说最优解法,也没问有多少种解决方案呢!看最后怎么问吧

  • 嗨起来 java开发 2015/09/26

    一个5块和一个10块在一起,然后让5块给10块,10块人买2张

  • J_Keita   2015/12/26

    $a=0;//记录5的人数
    $b=0;//记录10的人数
    $flag=0;//标记下次开始查找替换的位置的初始值
    $arr =[5,5,5,10,10,10,10,5,10,10,10,5,5,5,10,5,10,5,5,10,10,5,5,10];
    for($i = 0; $i$i){
    $j=$flag;
    }else{
    $j=$i+1;
    }
    if($a<$b){
    for(;$j<count($arr);$j++){
    if($arr[$j]==5){
    $arr[$i]=5;
    $arr[$j]=10;
    $flag=$j+1;
    $a++;
    $b–;
    break;
    }
    }
    }
    }
    var_dump($arr);

  • 圣灵洗脑机甲 兼职 Windows UWP 2015/12/26

    这…好像按金额排个序就解决问题了。让5块的先买票。

  • Alex   2016/04/26

    dp(i, j) 前i个人,j个人是5元的,然后转移

  • "菜鸟"   2016/04/27

    排列只需满足当前人(任意一个)可持10元的条件”前面5元人数不小于10元人数加一“即可

  • 龙雀 野生程序员 2016/04/27

    拿十块钱的一律去队尾就解决了。。

  • 沐沐 编辑 2016/05/04

    围观