首页 > 试题广场 >

马戏团

[编程题]马戏团
  • 热度指数：12236 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
搜狐员工小王最近利用假期在外地旅游，在某个小镇碰到一个马戏团表演，精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论，小王打听了下了解到， 马戏团正打算出一个新节目“最高罗汉塔”，即马戏团员叠罗汉表演。考虑到安全因素，要求叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相等。 团长想要本次节目中的罗汉塔叠的最高，由于人数众多，正在头疼如何安排人员的问题。小王觉得这个问题很简单，于是统计了参与最高罗汉塔表演的所有团员的身高体重，并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表，请找出可以叠出的最高罗汉塔的高度，这份表中马戏团员依次编号为1到N。

输入描述:
首先一个正整数N，表示人员个数。 
之后N行，每行三个数，分别对应马戏团员编号，体重和身高。


输出描述:
正整数m，表示罗汉塔的高度。
示例1

输入

6
1 65 100
2 75 80
3 80 100
4 60 95
5 82 101
6 81 70

输出

4
算法知识视频讲解
添加回答
日照香炉头像 日照香炉
动态规划，用到了最长上升子序列问题。首先按照体重从小到大排序，体重相同时，身高高的在上，然后求最长身高上升子序列的长度。 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct player
{
    int w;
    int h;
};
bool com_w(player p1,player p2)
{
     //按照体重从小到大排序 
     if(p1.w != p2.w)
     return p1.w <= p2.w;
     //在体重相等的条件下，身高高的在前（在上） 
     else
     return p1.h>p2.h;
}
int main(void)
{
    int N;
    int h;
    int w;
    int index;
    vector<player> p;
    while(cin>>N)
    {
        p.clear();
        
        for(int i = 0;i<N;i++)
        {
           player pt;
           cin>>index>>w>>h;
           pt.w = w;
           pt.h = h;
           p.push_back(pt);
        }  
        sort(p.begin(),p.end(),com_w);
        //按照身高求最大上升子序列 
        int dp2[N+1];
        int max = 0;
        dp2[0] = 1;
        for(int i = 1;i<N;i++)
        {
            dp2[i] = 1;
            for(int j = 0;j<i;j++)
            {
                if(p[j].h <= p[i].h && dp2[j]+1 > dp2[i])
                dp2[i] = dp2[j] + 1;
            }
        }
        for(int i = 0;i<N;i++)
        if(max < dp2[i])
        max = dp2[i];
        cout<<max<<endl;
    }
    system("pause");
    return 0;
}
发表于 2015-12-06 01:42:11 回复(19)
会呼吸旳痛头像 会呼吸旳痛 
//法一，排序求最长前序列
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Actor
{
	int height;
	int weight;
	Actor(int h,int w):height(h),weight(w)
	{}
	//bool operator<(const Actor &b)
	//{
	//	return (b.weight<this->weight) ||(b.weight==this->weight && b.height<=this->height);
	//}

};

bool compare(const Actor &a,const Actor &b)
{
	return (b.weight<a.weight) ||(b.weight==a.weight && b.height<=a.height);
}
int main()
{
	int n;
	while(cin>>n)
	{
		vector<Actor> actors;
		int id,h,w;
		int k=n;
		while(k--)
		{
			cin>>id>>h>>w;
			actors.push_back(Actor(h,w));
		}

		sort(actors.begin(),actors.end(),compare);
		vector<int>dp(n,0);
		dp[0] = 1;
		for(int i=1;i<n;i++)
		{
			int max = -1;
			for(int j =0;j<=i-1;j++)
			{
				if((actors[j].weight>actors[i].weight && actors[j].height>actors[i].height)||
					(actors[j].weight==actors[i].weight && actors[j].height>=actors[i].height))
				{
					if(dp[j]+1>max)max=dp[j]+1;
				}
			}
			if(max == -1)
				dp[i]=1;
			else
				dp[i] = max;
		}
			cout<<*max_element(dp.begin(),dp.end())<<endl;
	}
	return 0;
}
//法二
//不排序，dp递归求解能过90%，
//最后一个测试用例栈爆了
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int dp(int n,vector<vector<int>> &graph,vector<int> &len)
{
	if(len[n]>=0) return len[n];
	else
	{
		int max = -1;
		for(int i=0;i<graph.size();i++)
		{
			if(graph[i][n])
			{
				if(dp(i,graph,len)+1>max)
					max=dp(i,graph,len)+1;
			}
		}
		if(max==-1)
		{
			len[n] =1;
			return 1;
		}
		else
		{
			len[n]=max;
			return max;
		}
	}
}
int main()
{
	int n;
	
	while(cin>>n)
	{
		vector<pair<int,int>> actors;
		int id,h,w;
		int k=n;
		while(k--)
		{
			cin>>id>>h>>w;
			actors.push_back(make_pair(h,w));
		}

		vector<vector<int>> graph(n,vector<int>(n,0));
		for(int i=0;i<actors.size();i++)
			for(int j=i+1;j<actors.size();j++)
			{
				if(actors[i].first > actors[j].first && actors[i].second > actors[j].second)
					graph[i][j] =1;
				else if(actors[i].first >= actors[j].first && actors[i].second == actors[j].second)
					graph[i][j] =1;

				if(actors[i].first < actors[j].first && actors[i].second < actors[j].second)
					graph[j][i]=1;
				else if(actors[i].first <= actors[j].first && actors[i].second == actors[j].second)
					graph[j][i]=1;
			}

		vector<int> ans(n,-1);
		for(int i=0;i<graph.size();i++)
			dp(i,graph,ans);

		cout<<*max_element(ans.begin(),ans.end())<<endl;
	}
	return 0;
}

编辑于 2016-08-22 18:00:43 回复(0)
VagrantYang头像 VagrantYang 
package com.special.first;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * 搜狐01-马戏团（是我笨，还是题目表述不清楚）
 * 变形的最长上升子序列，加入了多关键字，需要自己先排序确定好要考察的顺序
 * 题意理解很重要，只有两种情况才可以叠在一起
 * 1.当体重不一样时，上面的身高要小于等于下面的身高
 * 2.当体重一样时，上面的身高要等于下面的身高
 *
 * 一种思路：我们按照体重为主序从小到大排序
 * 然后对于相同的体重，我们让身高的高在本次体重的最前面
 * 原因：因为我们动态规划里的判断条件只判断身高条件，且只要{0, i - 1}的身高比i的身高小于等于
 * 那么高度就加一，但是这样会造成体重情况的两人，由于第一个人的身高比第二人低，所以就会叠，但是这样是不合法。
 * 所以我们让相同体重的人，最高在前面，这时当两个人体重相同时，结合我们动态规划时的条件，只能身高一样才成立（对应合法的第二种）！
 * 而体重不一样，也就是上面的体重小于下面人的体重时，我们只需确保下面的人的身高大于等于上面的身高即可叠
 *
 * 我上面用的是递增求法，也可以递减求，见Pro059Improve1
 * Create by Special on 2018/3/9 16:14
 */
public class Pro059 {

    static class Node{
        int weight;
        int height;

        public Node(int weight, int height){
            this.weight = weight;
            this.height = height;
        }
    }

    public static int getMaxHeight(int n, Node[] nodes){
        int[] dp = new int[n];
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nodes[j].height <= nodes[i].height){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            Node[] nodes = new Node[n];
            int no;
            for(int i = 0; i < n; i++){
                no = input.nextInt();
                nodes[i] = new Node(input.nextInt(), input.nextInt());
            }
            Arrays.sort(nodes, new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    int less = o1.weight - o2.weight;
                    return less != 0 ? less : o2.height - o1.height;
                }
            });
            System.out.println(getMaxHeight(n, nodes));
        }
    }
}
发表于 2018-03-09 23:24:10 回复(1)
Java
在度假的秋田犬很喜欢飞来飞去头像 在度假的秋田犬很喜欢飞来飞去
测试用例有问题吧？？？？要么就是我太菜了看不懂这个测试用例
发表于 2022-04-17 17:39:12 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>

using namespace std;

struct person
{     int id;     int height;     int weight;
};

bool cmp(person a, person b)
{     if(a.weight != b.weight)         return a.weight < b.weight;     else         return a.height > b.height; 
}

int main()
{     int n;     while(cin>>n)     {         vector<person> v(n);         for(int i=0;i<n;i++)             cin>>v[i].id>>v[i].weight>>v[i].height;         sort(v.begin(), v.end(), cmp);         vector<int> dp(n,1);         int Max = 0;         for(int i=0;i<n;i++)         {             for(int j=0;j<i;j++)             {                 if((dp[i]<dp[j]+1) && v[i].height>=v[j].height)                     dp[i] = dp[j]+1;             }             if(dp[i] > Max)                 Max = dp[i];         }         cout<<Max<<endl;     }     return 0;
}

发表于 2017-12-16 00:38:32 回复(0)
夜小楼Dream头像 夜小楼Dream 
#Python版
#思路：最长递减子序列
#需要注意的是：  
#1、 比自己体重轻的时候，上边的人身高矮于自己或等于自己
#2、体重一样时，身高也要一样
# -*- coding:utf-8 -*-
import sys
class node:
    def __init__(self,ind,weight,height):
        self.ind = ind
        self.weight = weight
        self.height = height

def cmpNode(a,b):
    if a.height >b.height:
        return -1
    elif a.height <b.height:
        return 1
    else:
        if a.weight >b.weight:
            return -1
        elif a.weight <b.weight:
            return 1
        else:
            return 0

if __name__ == "__main__":
    while True:
        n = sys.stdin.readline().strip()
        if not n:
            break
        n = int(n)
        persons = []
        for i in range(n):
            n,v,h = [int(i) for i in sys.stdin.readline().strip().split(' ')]
            persons.append(node(n,v,h))
        persons.sort(cmp = cmpNode)
        dp = [0]*n
        for i in range(n):
            dp[i] = 1
            for j in range(i):
                if persons[i].weight < persons[j].weight and persons[i].height <= persons[j].height:
                    dp[i] = max(dp[i],dp[j]+1)
                elif persons[i].weight == persons[j].weight and persons[i].height == persons[j].height:
                    dp[i] = max(dp[i], dp[j] + 1)

        print max(dp)


发表于 2017-03-17 19:45:27 回复(0)
HelloWorldn头像 HelloWorldn
这道题题目有毒，不做这道题了！
发表于 2017-01-04 14:33:15 回复(0)
markCC头像 markCC
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
  
struct people{
    intw;
    inth;
};
intb[1000];
bool cmp(people people1, people people2){
  
    if(people1.w != people2.w)
        returnpeople1.w <= people2.w;
    else
    {
        returnpeople1.h> people2.h;
  
    }
  
  
}
  
intbSearch(intnum, intk)
{
    intlow = 1, high = k;
    while(low <= high)
    {
        intmid = (low + high) / 2;
        if(num >= b[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    returnlow;
}
  
  
  
intmain()
{
    
  
    intN;
  
    while(cin >> N)
    {
  
        vector<people> a;
        people temp;
        intw, h, row_num;
        for(inti = 0; i<N; i++){
  
  
            cin >> row_num>>w >> h;
            temp.w = w;
            temp.h = h;
            a.push_back(temp);
        }
        sort(a.begin(), a.end(), cmp);
  
        intlow = 1, hight = N;
        intk = 1;
        b[1] = a[0].h;
        for(inti = 1; i<N; i++)
        {
            if(a[i].h >= b[k])
                b[++k] = a[i].h;
            else
            {
                intpos = bSearch(a[i].h, k);
                b[pos] = a[i].h;
            }
        }
        cout << k << endl;
    }
  
  
    return0;
}
发表于 2016-03-24 12:48:35 回复(1)
王枫头像 王枫 
import java.util.Scanner;

public class Main { 
	public static class Dis{
		int Num;     //马戏团成员的编号
		int high;    //身高
		int weight;    //体重
		int max_high;  //记录这个马戏团成员为最下面的一个人，最多可以叠多少层罗汉
	}
	
	public static void main(String args[]){		 
		 Scanner cin = new Scanner(System.in);	    	 	
	     while(cin.hasNext()){  	 
	    	 int n = cin.nextInt();
	    	 Dis map[] = new Dis[n];
	    	 for(int i = 0;i < n;i++){
	    		 map[i] = new Dis();   //每次进入的元素插入队尾
	    		 map[i].Num = cin.nextInt();
	    		 map[i].weight = cin.nextInt();
	    		 map[i].high = cin.nextInt();
	    		 for(int j = i;j > 0;j--){    //使用冒泡排序，对新插入的元素插入队列，按照体重从小到大的顺序排序
	    			 if(map[j].weight < map[j-1].weight){
	    				 int Num = map[j].Num;
	    				 int high = map[j].high;
	    				 int weight = map[j].weight;
	    				 map[j].Num = map[j-1].Num;
	    				 map[j].high = map[j-1].high;
	    				 map[j].weight = map[j-1].weight;
	    				 map[j-1].Num = Num;
	    				 map[j-1].high = high;
	    				 map[j-1].weight = weight;
	    			 }else if(map[j].weight == map[j-1].weight &&map[j].high > map[j-1].high){  //如果体重相同，身高矮的在后面
	    				 int Num = map[j].Num;
	    				 int high = map[j].high;
	    				 int weight = map[j].weight;
	    				 map[j].Num = map[j-1].Num;
	    				 map[j].high = map[j-1].high;
	    				 map[j].weight = map[j-1].weight;
	    				 map[j-1].Num = Num;
	    				 map[j-1].high = high;
	    				 map[j-1].weight = weight;
	    			 }else
	    				 break;  //队列已经有序了，跳出循环
	    		 }
	    	 }	    	 
	    	 int max_high = getMaxHigh(map,n);
	    	 System.out.println(max_high);
	     }			 			 
	}

	private static int getMaxHigh(Dis[] map, int n) {
		// TODO Auto-generated method stub
		int max_high = 0;
		for(int i = 0;i < n;i++){
			map[i].max_high = 1;
			for(int j = 0; j < i;j++){
				if(map[i].high >= map[j].high && map[i].max_high < map[j].max_high+1){
					map[i].max_high = map[j].max_high + 1;
				}				
			}
			max_high = Math.max(max_high, map[i].max_high);
		}
		return max_high;
	}
}

发表于 2016-05-21 20:18:11 回复(1)
牛客845336号头像 牛客845336号
package test2;

import java.util.Scanner;

public class Interview {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = Integer.parseInt(scan.nextLine());
        int a[][] = new int[N][3];
        for (int i = 0; i < N; i++) {
            String str = scan.nextLine();
            String b[]=str.split(" ");
            for (int j = 0; j < 3; j++) {
                a[i][j]=Integer.parseInt(b[j]);
            }
        }
        for (int i = 0; i < N-1; i++) {
            for (int j = i+1; j < N; j++) {
                if(a[i][1]<=a[j][1]){
                    int b = a[i][1] ;
                    a[i][1] = a[j][1] ;
                    a[j][1]=b ;
                    int c = a[i][2] ;
                    a[i][2] = a[j][2] ;
                    a[j][2]=c ;
                }
            }
        }
        int count=N ;
        for (int i = 0; i < N-1; i++) {
            for (int j = i+1; j < N; j++) {
                if(a[i][2]<a[j][2]){
                    count-- ;
                }
            }
        }
        System.out.println(count);
    }
}
发表于 2015-11-17 11:52:52 回复(3)
詠恆啲诺琂头像 詠恆啲诺琂 
//体重相同时，只有身高也相同才可以站在自己肩上，比自己矮是不能站在自己肩上的。理解费劲，不说清楚。。

发表于 2016-08-08 17:18:58 回复(3)
Java
JustYoung头像 JustYoung 
 import java.util.*;

public class Main {
    
    static class People {
        int height;
        int weight;

        public People(int weight, int height) {
            this.height = height;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            People[] array = new People[n];
            for (int i = 0; i < n; ++i) {
                int index = scan.nextInt();
                array[index - 1] = new People(scan.nextInt(), scan.nextInt());
            }

            Arrays.sort(array, new Comparator<People>() {
                public int compare(People p1, People p2) {
                    int result = Integer.compare(p1.height, p2.height);
                    if (result != 0)
                        return result;
                    else
                        return Integer.compare(p1.weight, p2.weight);
                }
            });

            int[] dp = new int[n];
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < dp.length; ++i) {
                dp[i] = 1;
                for (int j = i - 1; j >= 0; --j) {
                    if (array[i].weight > array[j].weight
                        || (array[i].weight == array[j].weight && array[i].height == array[j].height)) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                max = Math.max(dp[i], max);
            }
            System.out.println(max);
        }
    }
}
妈蛋，切记，身高和体重要一起相等时，才能往上叠，其他情况下，都是要身高更矮，体重更轻才能往上叠。
编辑于 2016-08-30 13:42:45 回复(8)
C/C++
莫慢待made头像 莫慢待made 
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
struct unit
{
	int id;
	int weight;
	int height;
};
bool cmp(unit u1, unit u2){
	if(u1.weight != u2.weight) return u1.weight < u2.weight;
	else return u1.height > u2.height;
}
int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		vector<unit> vec(n);
		for(int i = 0; i < n; i++){
			scanf("%d%d%d", &vec[i].id, &vec[i].weight, &vec[i].height);
		}
		sort(vec.begin(), vec.end(), cmp);
		vector<int> dp(n,1);
		int max = -1;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < i; j++){
				if(dp[j]+1 > dp[i] && vec[i].height >= vec[j].height){
					dp[i] = dp[j]+1;
				}
			}
			if(dp[i] > max) max = dp[i];
		}
		printf("%d\n", max);
	}
}
思路：体重相同时， 只有身高相同才能叠。
 体重升序排列， 体重相同时，按身高降序排列（为了使index递增时， 不让体重相等，身高不等的人计为有效）。
接下来就是按照身高数据进行最大升序子序列。
发表于 2016-08-22 18:34:16 回复(3)
WillWu头像 WillWu
为什么如果身高相同的时候，要把体重重的排前面啊，不应该体重重的人在后面吗。
比如：
6
1 65 90
2 65 100
3 80 100
4 80 90
5 82 101
6 81 70
这个时候结果不应该是4吗？即编号为1-2-3-5.
可是如果对数据按照身高相同的时候，要把体重重的排前面的话，
就变成了
2 65 100
1 65 90
3 80 100
4 80 90
5 82 101
6 81 70
这个时候的结果就是3了，即编号为：2-3-5；
按照题目AC的程序是结果为3。谁给解答一下？
PS:看了别的回答里面有的回复，发现是这个原因：根据题意，“站在某个人肩上的人应该既比自己矮又比自己瘦，或相等”，因此只比自己矮或瘦的不应该站在自己肩上，如果身高高的排在后面，则跟自己相同体重，比自己矮的人会站到自己肩上，不符合题意。
也就是说，当如果两个人体重相同的情况下， 那么即便这个人比你矮了，他也不能站在你的肩膀上，而最长上升子序列的求法是只要后面的比你大，就计入+1.所以此时，为了不让这个跟你体重相同，但是比你矮的人站在你的肩膀上，只能把它放在你的后面，也就是身高高的放在前面。（这题目读懂也费劲）。 
struct actor
{
    int num;
    int height;
    int weight;
    int flag = false;
};
int main()
{
    int n;
    while(cin>>n)
    {
        struct actor person[1000];
        for(int i=0; i<n; i++)
        {
            int num,height,weight;
            cin>>num>>height>>weight;
            person[i].num = num;
            person[i].height = height;
            person[i].weight = weight;
        }
        for(int i=0; i<n-1; i++)
        {
            for(int j = 1; j<n-i; j++)
            {
                if(person[j-1].height>person[j].height)
                {
                    int temp = person[j].height;
                    person[j].height = person[j-1].height;
                    person[j-1].height = temp;

                    temp = person[j].weight;
                    person[j].weight = person[j-1].weight;
                    person[j-1].weight = temp;

                }
                else if(person[j-1].height==person[j].height)
                {
                    if(person[j-1].weight<person[j].weight)   //大于号就不对了
                    {
                        int temp = person[j].height;
                        person[j].height = person[j-1].height;
                        person[j-1].height = temp;

                        temp = person[j].weight;
                        person[j].weight = person[j-1].weight;
                        person[j-1].weight = temp;

                    }
                }
            }
        }
        int dp[n];
        memset(dp,0,10*sizeof(int));
        for(int i=0; i<n; i++)
        {
            dp[i] = 1;
            for(int j=0; j<=i-1; j++)
            {
                if(person[j].weight<=person[i].weight&&dp[i]<dp[j]+1)
                {
                    dp[i] = dp[j]+1;
                }
            }
        }
        int maxDp = 0;
        for(int i=0; i<n; i++)
        {
            if(maxDp<dp[i])
                maxDp = dp[i];
        }
        cout<<maxDp<<endl;
    }
}


编辑于 2016-07-15 14:46:16 回复(5)
乐天知命头像 乐天知命 
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
        while(in.hasNext()){ 
            int N = in.nextInt();
            int[][] a = new int[N][3];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < 3; j++) {
                    a[i][j] = in.nextInt();
                }
            }
            int m = getResult(N, a);
            System.out.println(m);
        }
	}
	private static int getResult(int N, int[][] a) {
		// TODO Auto-generated method stub
		for (int i = 0; i < N - 1; i++) {
			for (int j = i + 1; j < N; j++) {
				if (a[i][1] < a[j][1]) {
					int b = a[i][1];
					a[i][1] = a[j][1];
					a[j][1] = b;
					int c = a[i][2];
					a[i][2] = a[j][2];
					a[j][2] = c;
				} else if (a[i][1] == a[j][1] && a[i][2] > a[j][2]) {
					int b = a[i][1];
					a[i][1] = a[j][1];
					a[j][1] = b;
					int c = a[i][2];
					a[i][2] = a[j][2];
					a[j][2] = c;
				}
			}
		}
		int count[] = new int[N];
		for (int i = 0; i < N; i++) {
			count[i] = 1;
			for (int j = 0; j < i; j++) {
				if (a[j][2] >= a[i][2] && count[j] + 1 > count[i])
					count[i] = count[j] + 1;
			}
		}
		int max = 0;
		for (int i = 0; i < N; i++) {
			if (max < count[i]) {
				max = count[i];
			}
		}
		return max;
	}
}

发表于 2017-04-06 18:27:13 回复(0)
textbook头像 textbook
仔细想想其实不难，我们试想第一次按照体重进行排序，得到的结果是
1 60 95
2 65 100
3 75 80 
4 80 100
5 81 70
6 82 101
我们命名为weight[] height[]
这样就得到了按体重进行排序的对应结果，接下来我们按照身高排序
1 81 70
2 75 80
3 60 95
4 65 100
5  80 100
6 82 101
我们命名为otherweight[] height[]
好了，这个时候我们很容易从上到下推出他们的公共序列，一共为4个，但是如何制定一个法则来对两个数组的指针进行递增然后
进行比较还是让我纠结了一下，具体的
我们设置两个指针，分别指向第一个数组和第二个数组的下标，初始都为0，
第一次我们按照体重比较进行比较，如果发现当前的体重和升高相吻合，即可以将index1++, index2++
否则，我们让体重小的那个index++;遍历一遍计算出有多少个重复的序列count1;
第二次我们以身高为基准，同样，如果发现身高体重吻合，index1++, index2++
否则，我们让身高矮的那个index++,遍历一遍计算出有多少个重复的序列count2；
之后就很显然了 计算count1和count2的最大值
代码（含中间打印结果）
Scanner sc=new Scanner(System.in);
    while(sc.hasNext())
    {
    int n=sc.nextInt();
    int[] weight=new int[n];
    int[] height=new int[n];
    int[] otherweight=new int[n];
    int[] otherheight=new int[n];
    for(int i=0;i<n;++i)
    { 
                        //冒泡排序
    int index=sc.nextInt()-1;
    weight[index]=sc.nextInt();
    otherweight[index]=weight[index];
    height[index]=sc.nextInt();
    otherheight[index]=height[index];
    }
    for(int i=0;i<n;++i)
    {
    //冒泡排序
    for(int j=1;j<n-i;++j)
    {
    if(weight[j]<weight[j-1])
    {
    int temp1=weight[j];
    int temp2=height[j];
    weight[j]=weight[j-1];
    height[j]=height[j-1];
    weight[j-1]=temp1;
    height[j-1]=temp2;
    }
    }
    }
    for(int i=0;i<n;++i)
    System.out.println(weight[i]+" "+height[i]);
   
    for(int i=0;i<n;++i)
    {
    //chongpai
    for(int j=1;j<n-i;++j)
    {
    if(otherheight[j]<otherheight[j-1])
    {
    int temp1=otherweight[j];
    int temp2=otherheight[j];
    otherweight[j]=otherweight[j-1];
    otherheight[j]=otherheight[j-1];
    otherweight[j-1]=temp1;
    otherheight[j-1]=temp2;
    }
    }
    }
    for(int i=0;i<n;++i)
    System.out.println(otherweight[i]+" "+otherheight[i]);
    //各自为基准扫描两边
    int count1=0;
    int count2=0;
    int index1=0;
    int index2=0;
    while(index1<n&&index2<n)
    {
    //以体重为基准
    if(weight[index1]==otherweight[index2]&&height[index1]==otherheight[index2])
    {
    index1++;
    index2++;
    count1++;
    }
    else if(weight[index1]<otherweight[index2])
    {
    index1++;
    }
    else
    index2++;
    }
    index1=0;
    index2=0;
    while(index1<n&&index2<n)
    {
    //以身高为基准
    if(weight[index1]==otherweight[index2]&&height[index1]==otherheight[index2])
    {
    index1++;
    index2++;
    count2++;
    }
    else if(height[index1]<otherheight[index2])
    {
    index1++;
    }
    else
    index2++;
    }
    System.out.println(Math.max(count2, count1));
   
    
    	}

发表于 2016-08-02 11:56:53 回复(1)
连三月s头像 连三月s
***题目，爬
发表于 2022-03-08 10:57:52 回复(0)
yufeifly头像 yufeifly
代码就不附了。
这道题最坑爹的地方在于题意的理解。和自己一样重且比自己矮的人不能站在自己身上，和自己一样高且比自己轻的人也不能站在自己身上。
但我认为，题目根本没表述清除。
发表于 2017-08-16 08:42:54 回复(1)
牛客987680856号头像 牛客987680856号
不会出题就不要出题，浪费大家的时间。
实际的条件是x.weight<y.weight&&x.height<=y.height||x.weight==y.weight&&x.height==y.height
编辑于 2024-03-29 18:36:10 回复(0)
goForWork头像 goForWork
/*站在某个人肩上的人应该既比自己矮又比自己瘦，或相等 划重点
    要么等高等重要么又矮又搜
*/
#include <stdio.h>
int main() {
    int heightSize, k;
    int height[10000], weight[1000];
    while (scanf("%d", &heightSize)!=EOF) {
        for (int i = 0; i < heightSize; i++) {
            scanf("%d %d %d", &k, &height[i], &weight[i]);
        }
        for (int i = 0; i < heightSize; i++) { //按身高降序
            int flag = 0;
            for (int j = 0; j < heightSize - i - 1; j++) {
                if ((height[j] < height[j+1])
                    ||((height[j]==height[j+1])&&weight[j]<weight[j+1])){
                    int temp = height[j];
                    height[j] = height[j + 1];
                    height[j + 1] = temp;
                    temp = weight[j];
                    weight[j] = weight[j + 1];
                    weight[j + 1] = temp;
                    flag = 1;
                }
            }
            if (flag == 0)break;
        }
        //for(int i=0;i<heightSize;i++)printf("%d %d\n",height[i],weight[i]);
        int num[heightSize];
        for (int i = 0; i < heightSize; i++)num[i] = 1;
        int tempmax = 0;
        for (int low = 0, high = 1; high < heightSize; low++, high++) {//dp
            int max = 0;
            for (int j = 0; j <= low; j++) {
                //if (weight[j] >= weight[high] && height[j] > height[high])
                if (  (weight[j] > weight[high]&& height[j] > height[high])
                    ||(weight[j] == weight[high] && height[j] >= height[high]))
                    max = max > num[j] ? max : num[j];
            }
            num[high] += max;

            tempmax = tempmax > num[high] ? tempmax : num[high];
        }
        printf("%d\n", tempmax);
    }
}
发表于 2023-09-01 23:00:58 回复(0)
提交观点

问题信息

动态规划
来自：搜狐2016研发工程师编程题
难度：
58条回答 20233浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号