首页 > 代码库 > SHUOJ417解题报告

SHUOJ417解题报告

题目地址:

  http://acmoj.shu.edu.cn/problem/417/

题目概述:

  给定一个长度为n的非负整数序列,下标为0,1,…,n?1

  定义:sequence(K): 由下标为K的倍数组成的子序列,即下标为0,K,2K,...,[n?1/k]?k

  query(K,S): 询问sequence(K)中的第S大的数字

大致思路:

  这个题比赛的时候确实是大失误啊,本来想到了正解算法,但是随意分析了一下复杂度觉得应该是O(n2)的肯定过不了,然后以为是个什么可持久化线段树求第k大之类的,但是又不是询问区间遂放弃。

  做法其实挺容易想到的,直接离线处理所有的子区间,询问的时候对相应的子区间排序之后直接回答就好了。

复杂度分析:

  关键是复杂度的分析,当时觉得离线处理的复杂度是O(n2),然后询问的时候复杂度更高,应该是O(m*nlogn),这样肯定是过不了的。

  但是我们发现,对于一个k来说,它所对应的子区间长度是n/k,所以离线处理的复杂度应该是技术分享,而这个式子当n趋近于无穷大是应该是O(n*lnn)的,所以离线处理的复杂度应该是O(n*lnn)。

  对于询问来说,因为最多只有n个子区间,所以可以先将所有的询问按k值进行排序,这样可以使得对子区间的排序次数从m降到n,而对于子区间的排序,经过上面的分析之后很显然的知道不是O(nlogn),而是技术分享,对所有的子区间就是技术分享也就是O(n*lnn)。

  综上总的时间复杂度应该是O(n*lnn)。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <ctime>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

#define sacnf scanf
#define scnaf scanf
#define maxn 20010
#define maxm 100010
#define inf 1061109567
#define Eps 0.000001
const double PI=acos(-1.0);
#define mod 1000000007
#define MAXNUM 10000
#define For(i,j,k) for(int (i)=(j);(i)<=(k);(i)++)
#define mes(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ulld;
void Swap(int &a,int &b) {int t=a;a=b;b=t;}
ll Abs(ll x) {return (x<0)?-x:x;}

struct node
{
    int k,s,id;
} q[maxm];

vector<int> a[maxn];
int ans[maxm],x[maxn];

bool cmp(int a,int b) {return a>b;}

bool cmp1(node a,node b)
{
    if(a.k==b.k) return a.s<b.s;
    return a.k<b.k;
}

int main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    //clock_t st=clock();
    int T;scnaf("%d",&T);
    while(T--)
    {
        int n,m;scanf("%d%d",&n,&m);
        For(i,1,n) a[i].clear();
        For(i,0,n-1) scanf("%d",&x[i]);
        for(int i=1;i*i<=n;i++)
            for(int j=0;j<n;j+=i) a[i].push_back(x[i]);
        For(i,1,m)
        {
            scanf("%d%d",&q[i].k,&q[i].s);
            if(q[i].k>=n) q[i].k=n;q[i].id=i;
        }
        sort(q+1,q+1+m,cmp1);
        For(i,1,m)
        {
            if(q[i].k*q[i].k>=n)
            {
                for(int j=0;j<n;j+=q[i].k) a[q[i].k].push_back(x[j]);
            }
            sort(a[q[i].k].begin(),a[q[i].k].end(),cmp);
            int t=i,len=a[q[i].k].size();
            while(q[t].k==q[i].k)
            {
                if(q[t].s>len) ans[q[t].id]=-1;
                else ans[q[t].id]=a[q[i].k][q[t].s-1];
                t++;
            }
            i=t-1;
        }
        For(i,1,m) printf("%d\n",ans[i]);
    }
    //clock_t ed=clock();
    //printf("\n\nTime Used : %.5lf Ms.\n",(double)(ed-st)/CLOCKS_PER_SEC);
    return 0;
}

 

SHUOJ417解题报告