「JoyOI1463」智商问题

2014年3月4日4,5213

背景 Background

各种数据结构帝~
各种小姊妹帝~
各种一遍AC帝~ 来吧！

描述 Description

某个同学又有很多小姊妹了
他喜欢聪明的小姊妹所以经常用神奇的函数来估算小姊妹的智商
他得出了自己所有小姊妹的智商
小姊妹的智商都是非负整数
但是这个同学看到别的同学的小姊妹
也喜欢用神奇的函数估算一下
然后看看这个小姊妹在自己的小姊妹群体中排在第几位…
(这么邪恶的兴趣…)

输入格式 InputFormat

第一行一个整数N 代表小姊妹的个数
第二行N个整数代表这位同学N个小姊妹的智商
接下来若干行每行一个整数
代表这位同学看中的别人的小姊妹的智商
0<=智商<=2^31-1
0<=N<=1000000

输出格式 OutputFormat

输出若干行
每行一个整数回答新的小姊妹
在原来小姊妹中智商的排名

样例输入 SampleInput [复制数据]

1 2 3 4 5

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

数据量很大
C语言用scanf输入输出!
另外这个同学的小姊妹群体在这个题中是不会变的~
他会在看完所有别的同学的小姊妹之后…
大家听说过苏格拉底和麦田的故事的吧…

题解

这题是个二分的简单题

不过可以用来练习分块，将a数组排序之后分为√n块，记录一下每一块的最大值

每次询问先√n枚举找到这个数所在的块，再在块内暴力√n个元素

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,t,a[1000005];
int last[1005];
int query(int x)
{
    if(x>a[n])return n+1;
    if(x<a[1])return 1;
    for(int i=1;i<=t+1;i++)
        if(x<=last[i]&&x>last[i-1])
        {
            int b=(i-1)*t;
            for(int j=1;j<=t;j++)
                if(a[b+j]>=x)return (b+j);
        }
}
int main()
{
    n=read();
	for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+n+1);
    t=sqrt(n);
    for(int i=1;i<=t;i++)
        last[i]=a[t*i];
    last[t+1]=a[n];
    int x;
	while(scanf("%d",&x)!=EOF)
		printf("%d\n",query(x));
	return 0;
}

#include<cmath>

#include<cstdio>

#include<iostream>

#include<algorithm>

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,t,a[1000005];

int last[1005];

int query(int x)

{

if(x>a[n])return n+1;

if(x<a[1])return 1;

for(int i=1;i<=t+1;i++)

if(x<=last[i]&&x>last[i-1])

{

int b=(i-1)*t;

for(int j=1;j<=t;j++)

if(a[b+j]>=x)return (b+j);

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

a[i]=read();

sort(a+1,a+n+1);

t=sqrt(n);

for(int i=1;i<=t;i++)

last[i]=a[t*i];

last[t+1]=a[n];

int x;

while(scanf("%d",&x)!=EOF)

printf("%d\n",query(x));

return 0;

}

「BZOJ3343」教主的魔法 »

zyf2000

黄学长，为什么我把last数组存成下标，然后每次查询的时候套上a，这样就会T掉一组。

李孜睿

老老实实写二分呗，

zyf2000

。。那我就要练分块。。

hzwer.com _ Home | http://hzwer.com

「JoyOI1463」智商问题

背景 Background

描述 Description

输入格式 InputFormat

输出格式 OutputFormat

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

题解

分类目录

热门文章

Myfriends

近期评论