SH1. 马戏团
描述
搜狐员工小王最近利用假期在外地旅游，在某个小镇碰到一个马戏团表演，精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论，小王打听了下了解到， 马戏团正打算出一个新节目“最高罗汉塔”，即马戏团员叠罗汉表演。考虑到安全因素，要求叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相等。 团长想要本次节目中的罗汉塔叠的最高，由于人数众多，正在头疼如何安排人员的问题。小王觉得这个问题很简单，于是统计了参与最高罗汉塔表演的所有团员的身高体重，并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表，请找出可以叠出的最高罗汉塔的高度，这份表中马戏团员依次编号为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
C 解法, 执行用时: 2ms, 内存消耗: 320KB, 提交时间: 2021-08-07
#include <stdio.h>
#include <stdlib.h>
typedef struct Human{
int height;
int weight;
}HumanNode;
int cmp(const void* _a, const void* _b){
HumanNode* a = (HumanNode*)_a;
HumanNode* b = (HumanNode*)_b;
if (a->weight == b->weight){
return b->height - a->height;
}
return a->weight - b->weight;
}
int main(){
int num;
int i, tmp, max, left, right, mid;
while(~scanf("%d", &num)){
int min_height[num];
HumanNode human[num];
for (i = 0; i < num; i++){
scanf("%d %d %d", &tmp, &human[i].weight, &human[i].height);
}
qsort(human, num, sizeof(HumanNode), cmp);
min_height[0] = human[0].height;
max = 1;
for (i = 1; i< num; i++){
if (human[i].height >= min_height[max-1]){
max++;
min_height[max-1] = human[i].height;
}
else{
left = 0;
right = max - 1;
while (left <= right){
mid = left + (right - left) / 2;
if (human[i].height >= min_height[mid]){
left = mid + 1;
}
else{
right = mid - 1;
}
}
min_height[left] = human[i].height;
// for (j = 0; j < max; j++){
// if (human[i].height < min_height[j]){
// min_height[j] = human[i].height;
// break;
// }
// }
}
}
printf("%d\n", max);
}
}
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2017-08-28
/**
* 先对体重从小到大排序
* 再对身高求最长递增子序列
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct person {
int id;
int weight;
int height;
} Person;
/**
* 依体重从小到大排序
* 相等则身高高的排在前面
*/
int compare(const void *a, const void *b) {
Person *p1 = (Person *) a;
Person *p2 = (Person *) b;
if (p1->weight != p2->weight) {
return p1->weight >= p2->weight;
} else {
return p1->height < p2->height;
}
}
/**
* 找到刚好大于x的数,数组下标
*/
int binarySearch(int *arr, int len, int x) {
int mid;
int left = 0;
int right = len - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (arr[mid] <= x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
int lis(Person *p, int n, int *maxv) {
int pos, temp;
maxv[0] = p[0].height;
int len = 1;
for (int i = 1; i < n; ++i) {
temp = p[i].height;
if (temp >= maxv[len - 1]) {//身高可以相等
maxv[len++] = temp;
} else {
pos = binarySearch(maxv, len, temp);
maxv[pos] = temp;
}
}
return len;
}
int main() {
int n;
while (scanf("%d", &n) != EOF) {
int maxv[n + 1];
Person p[n + 1];
for (int i = 0; i < n; ++i) {
scanf("%d %d %d", &p[i].id, &p[i].weight, &p[i].height);
}
qsort(p, n, sizeof(p[0]), compare);
printf("%d\n", lis(p, n, maxv));
}
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 348KB, 提交时间: 2022-08-02
#include <stdio.h>
#include <stdlib.h>
typedef struct Human{
int height;
int weight;
}HumanNode;
int cmp(const void* _a, const void* _b){
HumanNode* a = (HumanNode*)_a;
HumanNode* b = (HumanNode*)_b;
if (a->weight == b->weight){
return b->height - a->height;
}
return a->weight - b->weight;
}
int main(){
int num;
int i, tmp, max, left, right, mid;
while(scanf("%d", &num)!=EOF){
int min_height[num];
HumanNode human[num];
for (i = 0; i < num; i++){
scanf("%d %d %d", &tmp, &human[i].weight, &human[i].height);
}
qsort(human, num, sizeof(HumanNode), cmp);
min_height[0] = human[0].height;
max = 1;
for (i = 1; i< num; i++){
if (human[i].height >= min_height[max-1]){
max++;
min_height[max-1] = human[i].height;
}
else{
left = 0;
right = max - 1;
while (left <= right){
mid = left + (right - left) / 2;
if (human[i].height >= min_height[mid]){
left = mid + 1;
}
else{
right = mid - 1;
}
}
min_height[left] = human[i].height;
// for (j = 0; j < max; j++){
// if (human[i].height < min_height[j]){
// min_height[j] = human[i].height;
// break;
// }
// }
}
}
printf("%d\n", max);
}
}
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-09-05
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Node{
int w, h;
};
bool cmp(Node a, Node b) {
if(a.w != b.w) return a.w <= b.w;
return a.h > b.h;
}
int main() {
int n, h, w, idx;
while(cin >> n) {
vector<Node> a;
for(int i = 0; i < n; i++) {
cin >> idx >> w >> h;
a.push_back({w, h});
}
sort(a.begin(), a.end(), cmp);
vector<int> f(n+1), q(n+1);
int len = 0;
for(int i = 0; i < n; i++) {
int l = 0, r = len;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(q[mid] > a[i].h) r = mid - 1;
else l = mid;
}
q[r+1] = a[i].h;
len = max(len, r+1);
}
cout << len << endl;
}
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 380KB, 提交时间: 2020-10-31
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Node{
int w, h;
};
bool cmp(Node a, Node b) {
if(a.w != b.w) return a.w <= b.w;
return a.h > b.h;
}
int main() {
int n, h, w, idx;
while(cin >> n) {
vector<Node> a;
for(int i = 0; i < n; i++) {
cin >> idx >> w >> h;
a.push_back({w, h});
}
sort(a.begin(), a.end(), cmp);
vector<int> f(n+1), q(n+1);
int len = 0;
for(int i = 0; i < n; i++) {
int l = 0, r = len;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(q[mid] > a[i].h) r = mid - 1;
else l = mid;
}
q[r+1] = a[i].h;
len = max(len, r+1);
}
cout << len << endl;
}
return 0;
}