题解 | #彩虹岛套娃#
彩虹岛套娃
https://ac.nowcoder.com/acm/problem/14674
题号：NC14674 链接：https://ac.nowcoder.com/acm/problem/14674
来源：牛客网
题目描述
俄罗斯套娃是俄罗斯特产的木制玩具，一般由多个一样图案的空心木娃娃一个套一个组成，最多可达十多个，通常为圆柱形，底部平坦可以直立。颜色有红色，蓝色，绿色，紫色等。最普通的图案是一个穿着俄罗斯民族服装的姑娘，叫做“玛特罗什卡”，这也成为这种娃娃的通称。
彩虹岛也有自己的套娃，不过与俄罗斯套娃有所不同，其组成规则如下：
-
空心木娃娃只有正方体与球两种形状。
-
正方体娃娃与球体娃娃可以相互套，也可以相同形状之间套。
-
当两形状相切的时候使能够互相嵌套的，比如半径为2的球体能套在边长为4的正方体中。
-
所有木娃娃的厚度可以忽略不计。
现在有𝑛个正方体和𝑚个球形的木娃娃，其中第𝑖个正方体娃娃边长为𝑎𝑖，第𝑗个球形娃娃半径为𝑟𝑗。用这些娃娃组成一个套娃，最多有几层？ 数据保证所有正方体边长不相同，所有的圆半径不相同。
输入
1
3 4
2 4 6
7 5 3 1
输出
5
思路： 这道题可以采用dp思路（动态规划）。
dp[i] = max(dp[j] + 1, ....) 其中j满足第i个套娃可以套第j个套娃的所有j，且i!=j.
难点在于，这道题的复杂度要求比较高，直接O(n^2)也是被pass的。 需要求解上面的公式，要做到：
1.先算出所有的dp[j]值，再算dp[i].
2.求解max不能直接遍历求解，不然复杂度便是O(n^2).
针对第一个问题比较简单： 按照一定的规则排序，保证j在i的排序前面，然后按照排序进行计算即可。这个排序，可以按照如下的排序规则获得（其中一种）：
排序规则：如果是球体，其权重值为2*R，如果是正方体，其权重值为L。如果权重一致，正方体是大于球体（正方体恰好套球体），正方体排在球体后面。
很容易证明，这个排序，小正方体在大正方体的排序前面（显然），小球体在大球体的排序前面（显然）。正方体能够套住的所有球体，所有球体都在其排序前面（显然）。球体能够套住的正方体，所有正方体也在其排序前面（这个推一下也是显然的）
第二个问题：如何求解max值，其实可以优化，优化成： dp[i]=max(dp[j1], dp[j2]),
其中第j1个套娃的类型跟第i个套娃的类型一致，并且第j1个套娃是在排序中最接近第i个套娃的，或者说，第j1个套娃是同类型中，比第i个套娃次小的那个套娃。
其中第j2个套娃的类型跟第i个套娃的类型不一致，并且第j2个套娃是在能够被套得住的排序中最接近第i个套娃的不同类型套娃。
求最接近套娃的求法，可以在遍历算dp[i]的时候，顺便算出最接近的套娃，比如同类型的，在遍历中取上一次同一个同类型套娃值即可，因此复杂度为O(n).
需要注意的是第一个问题的，涉及到排序，排序最快是O(n*log(n)).排序不能使用类似冒泡排序等复杂度较高的排序，可以使用不稳定排序，比如堆排序，但快排（最坏是O(n^2)）可能不行。
附代码：
// dddd.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define MAX(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef struct Node{
int type;
long long len;
int id;
}Node;
Node data2[200020];
int dp[200020];
int NodeCmp(Node *x, Node *y) {
if (x->type == y->type) {
if (x->len > y->len) return 1;
if (x->len < y->len) return -1;
}
else {
int a = x->type == 1 ? x->len : 2 * x->len;
int b = y->type == 1 ? y->len : 2 * y->len;
if (a > b||a==b&&x->type==1) return 1;
if (a < b||a==b&&y->type==1) return -1;
}
return 0;
}
template<class Class>
void duisort(Class*s, Class *e, int (*cmp)(Class*, Class*)) {
// 大顶堆初始化
int len = e - s;
Node* duiTop = s - 1;
for (int i = len / 2; i >= 1; i--) {
// 下沉
int ii = i;
while (2 * ii <= len) {
int j = 2 * ii;
if (j + 1 <= len && cmp(duiTop + j + 1, duiTop + j) > 0) j++;
if (cmp(duiTop + ii, duiTop + j) < 0) {
Node x = duiTop[ii];
duiTop[ii] = duiTop[j];
duiTop[j] = x;
}
else break;
ii = j;
}
}
for (int i = len; i >=2; i--) {
Node x = duiTop[i];
duiTop[i] = duiTop[1];
duiTop[1] = x;
// 下沉
int ii = 1;
while (2 * ii <= i - 1) {
int j = 2 * ii;
if (j + 1 <= i-1 && cmp(duiTop + j + 1, duiTop + j) > 0) j++;
if (cmp(duiTop + ii, duiTop + j) < 0) {
Node x = duiTop[ii];
duiTop[ii] = duiTop[j];
duiTop[j] = x;
}
else break;
ii = j;
}
}
}
int main() {
//如果半径R和正方形L满足4 * R * R >= 3 * L * L, 球可以套正方体
//如果半径R和正方形L满足L >= 2*R, 正方体可以套球
int t;
//freopen("1.txt", "r", stdin);
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
data2[i].type = 1;
cin >> data2[i].len;
}
for (int i = 0; i < m; i++) {
cin >> data2[i + n].len;
data2[i + n].type = 2;
}
Node temp;
// 进行排序
n += m;
duisort(data2, data2 + n, NodeCmp);
int dpSameLastValue[3] = { 0,-1,-1 };
int dpNoSameLastKey[3] = { 0,0,0 };
int ret = 0;
for (int i = 0; i < n; i++) {
data2[i].id = i+1;
//cout << "I: 类型:" << (data2[i].type == 1 ? "正方体" : "球体") << " " << data2[i].len << endl;
dp[i] = dpSameLastValue[data2[i].type] + 1;
int otherType = 3 - data2[i].type;
while (dpNoSameLastKey[otherType] < i) {
// 如果找到可能小于自己的非同类型
if (data2[dpNoSameLastKey[otherType]].type == otherType) {
// 是否可以套住
if (data2[i].type == 1 && data2[i].len >= 2 * data2[dpNoSameLastKey[otherType]].len ||
data2[i].type == 2 && 4 * data2[i].len * data2[i].len >= 3 * data2[dpNoSameLastKey[otherType]].len * data2[dpNoSameLastKey[otherType]].len) {
//cout << "I: 套住 " << (i + 1) << "->" << data2[dpNoSameLastKey[otherType]].id << " max(" << dp[i] << "," << (dp[dpNoSameLastKey[otherType]] + 1) << ")" << endl;
dp[i] = MAX(dp[i], dp[dpNoSameLastKey[otherType]] + 1);
}
else {
break;
}
}
dpNoSameLastKey[otherType]++;
}
dpSameLastValue[data2[i].type] = dp[i];
ret = MAX(ret, dp[i] + 1);
//cout << "I: 结果 第" << (i + 1) << " -->" << dp[i]<<endl<<endl;
}
cout << ret << endl;
}
return 0;
}
投递峰飞航空等公司10个岗位 >
查看20道真题和解析