2011-0052

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：[[br]]
有N个人要去看电影，每次一个人买票，其座位号为当前（前面的人坐下时）第Ai个座位。求每个人最后真正的座位号。[[br]]
解法[[br]]
模拟题，每次依次让一个人买票，然后用数据结构维护（线段树，树状数组等），用二分法找到真正的座位号。[[br]]
时间复杂度O(n (log n)^2^)，也可以做到O(n log n)[[br]]
{{{
#include<cstdio>
#include<cstring>

int n,t,q;
int a[50010],s[50010];
bool x[50010];

void add(int k)
{
    x[k] = true;
    for(int i = k;i <= n;i +=(i & (-i))) s[i]++;
}

void del(int k)
{
    x[k] = false;
    for(int i = k;i <= n;i +=(i & (-i))) s[i]--;
}

int find(int k)
{
    int ret = 0,sum = 0,q = 1;
    while(q < n) q *= 2;
    if (q > n) q /= 2;
    while(q > 0)
    {
        if (ret+q <= n)
        {
            if (sum + s[ret+q] < k)
            {
                ret += q;
                sum += s[ret];
            } else
            if ((sum + s[ret+q] == k)&&(x[ret+q]))
            {
                ret += q;
                sum += s[ret];
                break;
            }
        }
        q /= 2;
    }
    return ret;
}

int main()
{
    while(scanf("%d",&n) != EOF)
    {
        memset(s,0,sizeof(s));
        for(int i = 1;i <= n;i++) add(i);
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&t);
            a[i] = find(t);
            del(a[i]);
        }
        scanf("%d",&q);
        for(int i = 1;i < q;i++)
        {
            scanf("%d",&t);
            printf("%d ",a[t]);
        }
        scanf("%d",&t);
        printf("%d\n",a[t]);
    }
    return 0;
}
}}}
by luyi

题目大意：[[br]]

有N个人要去看电影，每次一个人买票，其座位号为当前（前面的人坐下时）第Ai个座位。求每个人最后真正的座位号。[[br]]

解法[[br]]

模拟题，每次依次让一个人买票，然后用数据结构维护（线段树，树状数组等），用二分法找到真正的座位号。[[br]]

时间复杂度O(n (log n)²)，也可以做到O(n log n)[[br]]

#include<cstdio>
#include<cstring>
int n,t,q;
int a[50010],s[50010];
bool x[50010];
void add(int k)
{
    x[k] = true;
    for(int i = k;i <= n;i +=(i & (-i))) s[i]++;
}
void del(int k)
{
    x[k] = false;
    for(int i = k;i <= n;i +=(i & (-i))) s[i]--;
}
int find(int k)
{
    int ret = 0,sum = 0,q = 1;
    while(q < n) q *= 2;
    if (q > n) q /= 2;
    while(q > 0)
    {
        if (ret+q <= n)
        {
            if (sum + s[ret+q] < k)
            {
                ret += q;
                sum += s[ret];
            } else
            if ((sum + s[ret+q] == k)&&(x[ret+q]))
            {
                ret += q;
                sum += s[ret];
                break;
            }
        }
        q /= 2;
    }
    return ret;
}
int main()
{
    while(scanf("%d",&n) != EOF)
    {
        memset(s,0,sizeof(s));
        for(int i = 1;i <= n;i++) add(i);
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&t);
            a[i] = find(t);
            del(a[i]);
        }
        scanf("%d",&q);
        for(int i = 1;i < q;i++)
        {
            scanf("%d",&t);
            printf("%d ",a[t]);
        }
        scanf("%d",&t);
        printf("%d\n",a[t]);
    }
    return 0;
}

by luyi