0

我最近正在研究以下问题。 http://www.codechef.com/problems/D2

主厨正在为 DirectiPlex 就职派对策划自助餐，并邀请了所有人。在他们进来的路上，每位客人都会拿起一张纸，里面有一个随机数字（这个数字可以重复）。客人们随后与他们的朋友坐在圆桌旁。厨师现在决定他想玩一个游戏。他让你从你的桌子上随机挑选一个人，让他们大声读出他们的号码。然后，围绕桌子顺时针移动，每个人都会读出他们的号码。目标是找到形成递增子序列的那组数字。所有拥有这些号码的人都将有资格参加幸运抽奖！一位软件开发人员对这一前景感到非常兴奋，并希望最大限度地增加有资格参加幸运抽奖的人数。所以，他决定编写一个程序来决定谁应该先读取他们的号码，以最大限度地增加有资格参加幸运抽奖的人数。你能打败他吗？

输入

第一行包含t测试用例的数量（大约 15 个）。然后是t测试用例。每个测试用例由两行组成：

  1. 第一行包含一个数字N，即被邀请参加聚会的客人人数。
  2. 第二行包含以空格分隔的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);
4

1 回答 1

0

该算法只是简单地在起点进行猜测，并为每个猜测计算 LIS。

LIS 中的第一个值可能是一个很小的数字，因此该算法只是尝试将 LIMIT 最小值作为潜在的起点。

排序函数用于识别最小值。

for 循环用于依次检查每个起点。

警告

请注意，对于某些输入，此算法可能会失败。例如，考虑序列

0,1,2,..,49,9900,9901,...,99999,50,51,52,...,9899

该算法将仅尝试前 37 个起点，而错过 50 处的最佳起点。

您可以通过将代码更改为：

int main() {
    int t;
    t=1;
    while (t--) {
    N=10000;
        vector<node> list;
        int i;
        for (i = 0; i < N; i++) {
            node temp;
        if (i<50)
        g[i]=i;
        else if (i<150)
            g[i]=9999-150+i;
        else
            g[i]=i-100;
            temp.val = g[i];
            temp.index = i;
            list.push_back(temp);
        }
        sort(list.begin(), list.end(), cmp);
        cout << solve(g, list) << endl;
    }
    return 0;
}

这将根据 LIMIT 是 37 还是 370 生成不同的答案。

在实践中，对于随机生成的序列，它很有可能工作（尽管我不知道如何准确计算概率）。

于 2014-09-22T17:47:16.793 回答