我最近正在研究以下问题。 http://www.codechef.com/problems/D2
主厨正在为 DirectiPlex 就职派对策划自助餐，并邀请了所有人。在他们进来的路上，每位客人都会拿起一张纸，里面有一个随机数字（这个数字可以重复）。客人们随后与他们的朋友坐在圆桌旁。厨师现在决定他想玩一个游戏。他让你从你的桌子上随机挑选一个人，让他们大声读出他们的号码。然后，围绕桌子顺时针移动，每个人都会读出他们的号码。目标是找到形成递增子序列的那组数字。所有拥有这些号码的人都将有资格参加幸运抽奖！一位软件开发人员对这一前景感到非常兴奋，并希望最大限度地增加有资格参加幸运抽奖的人数。所以，他决定编写一个程序来决定谁应该先读取他们的号码，以最大限度地增加有资格参加幸运抽奖的人数。你能打败他吗？
输入
第一行包含t测试用例的数量（大约 15 个）。然后是t测试用例。每个测试用例由两行组成：
- 第一行包含一个数字
N，即被邀请参加聚会的客人人数。 - 第二行包含以空格分隔的
N数字a1, a2, ..., an，即按顺时针顺序写在纸上的数字。
输出
对于每个测试用例，打印一个包含单个数字的行，该数字是有资格参加抽奖的客人的最大数量。
约束
1 ≤ N ≤ 10000
您可以假设纸上的每个数字编号；ai是随机生成的，即可以以相等的概率出现区间 中的任何数字[0,U]，其中U是某个上界 ( 1 ≤ U ≤ 106)。
例子
输入：
3
2
0 0
3
3 2 1
6
4 8 6 1 5 2
输出：
1
2
4
在检查解决方案时，我发现了这段代码：
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#define LIMIT 37
using namespace std;
struct node {
int val;
int index;
};
int N;
int binary(int number, vector<int>& ans) {
int start = 0;
int n = ans.size();
int end = n - 1;
int mid;
if (start == end)
return 0;
while (start != end) {
mid = (start + end) / 2;
if (ans[mid] == number)
break;
if (ans[mid] > number)
end = mid;
else
start = mid + 1;
}
mid = (start + end) / 2;
return mid;
}
void display(vector<int>& list) {
cout << endl;
for (int i = 0; i < list.size(); i++)
cout << list[i] << " ";
cout << endl;
}
int maxsubsequence(vector<int>& list) {
vector<int> ans;
int N = list.size();
ans.push_back(list[0]);
int i;
// display(list);
for (i = 1; i < N; i++) {
int index = binary(list[i], ans);
/*if(index+1<ans.size())
continue;*/
if (list[i] < ans[index])
ans[index] = list[i];
if (list[i] > ans[index])
ans.push_back(list[i]);
// display(ans);
}
return ans.size();
}
int compute(int index, int* g) {
vector<int> list;
list.push_back(g[index]);
int itr = (index + 1) % N;
while (itr != index) {
list.push_back(g[itr]);
itr = (itr + 1) % N;
}
return maxsubsequence(list);
}
int solve(int* g, vector<node> list) {
int i;
int ret = 1;
for (i = 0; i < min(LIMIT, (int)list.size()); i++) {
// cout<<list[i].index<<endl;
ret = max(ret, compute(list[i].index, g));
}
return ret;
}
bool cmp(const node& o1, const node& o2)
{ return (o1.val < o2.val); }
int g[10001];
int main() {
int t;
cin >> t;
while (t--) {
cin >> N;
vector<node> list;
int i;
for (i = 0; i < N; i++) {
node temp;
cin >> g[i];
temp.val = g[i];
temp.index = i;
list.push_back(temp);
}
sort(list.begin(), list.end(), cmp);
cout << solve(g, list) << endl;
}
return 0;
}
谁可以给我解释一下这个。我很清楚在 nlog(n) 中计算 LIS。我无法理解的是这部分：
int ret = 1;
for (i = 0; i < min(LIMIT, (int)list.size()); i++) {
// cout<<list[i].index<<endl;
ret = max(ret, compute(list[i].index, g));
}
以及排序背后的原因
sort(list.begin(),list.end(),cmp);