首页 > 代码库 > POJ 2828 poj 2828 Buy Tickets 【树状数组,已知前n项和为K,返回n值】

POJ 2828 poj 2828 Buy Tickets 【树状数组,已知前n项和为K,返回n值】

题目链接:http://poj.org/problem?id=2828

在一个队列中,一个人想要插队,告诉你每个新来的人会插在i个人后面,求出最后的队列。

如果我们用模拟的话,那么时间复杂度肯定是超了;想想,如果我们逆序,那么最后来的人的位置一定是固定的,这样的话,我们将问题转化成逆序扫描给出数据,插在i个人后面这个数据就变成了在这个人前面需要留出多少个空位。如此我们只需要用树状数组记录前n项总共有多少个空位,每扫描一个数据,就找出能使得他前面正好有i个空位。

这题用树状数组或者线段树都可以,今天写了树状数组的。开始不知道有那个已知前n项和为K,返回n值的函数,就用二分查找了那个值,差点就T了,后来改用那个函数,节省了差不多一秒种。

代码(二分):

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 200020
using namespace std;
int n;
int a[N];
int c[N];
int ans[N];
struct fuck
{
    int x,num;
}peo[N];
int add(int x,int a)
{
    for(int i=x;i<=n;i+=(i&(-i)))
    {
        c[i]+=a;
    }
}
int getsum(int i)
{
    int cnt=0;
    while(i>=1)
    {
        cnt+=c[i];
        i-=(i&(-i));
    }
    return cnt;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=n;i>=1;i--)
        {
            scanf("%d%d",&peo[i].x,&peo[i].num);
            add(i,1);
        }
        for(int i=1;i<=n;i++)
        {
            int temp=peo[i].x;
            int lb=0,ub=n+1;
            while(ub-lb>1)
            {
                int mid=(ub+lb)/2;
                if(getsum(mid)>temp)
                    ub=mid;
                else
                    lb=mid;
            }
            add(ub,-1);
            ans[ub]=peo[i].num;
        }
        for(int i=1;i<=n;i++)
            printf("%d%c",ans[i]," \n"[i==n]);
    }
    return 0;
}


使用那个函数的代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 200020
using namespace std;
int n;
int a[N];
int c[N];
int ans[N];
struct fuck
{
    int x,num;
}peo[N];
int add(int x,int a)
{
    for(int i=x;i<=n;i+=(i&(-i)))
    {
        c[i]+=a;
    }
}
int getsum(int i)
{
    int cnt=0;
    while(i>=1)
    {
        cnt+=c[i];
        i-=(i&(-i));
    }
    return cnt;
}
int getK(int K)
{
    int ans = 0,cnt=0;
    for(int i=18;i>=0;i--)//i>=0
    {
        ans+=(1<<i);
        if(ans>=n||cnt+c[ans]>=K) ans-=(1<<i);
        else cnt+=c[ans];
    }
    return ans+1;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&peo[i].x,&peo[i].num);
            add(i,1);
        }
        for(int i=n;i>=1;i--)
        {
            int temp=peo[i].x;
//            int lb=0,ub=n+1;
//            while(ub-lb>1)
//            {
//                int mid=(ub+lb)/2;
//                if(getsum(mid)>temp)
//                    ub=mid;
//                else
//                    lb=mid;
//            }
            int ub=getK(temp+1);
            ans[ub]=peo[i].num;
            add(ub,-1);
        }
        for(int i=1;i<=n;i++)
            printf("%d%c",ans[i]," \n"[i==n]);
    }
    return 0;
}