[C++知识库]ZCMU--1488: 过家家。。。(C语言)

Description

开学的那段时间，大一的小鲜肉门都被学姐带着玩过游戏吧，其中有一种就是过家家，但是把谁叫出来做游戏是一个很麻烦的事情，因为彼此都不认识，而且小鲜肉们都很羞涩 = = ，于是你们的学姐找学长想了个办法： 假设有n个人玩过家家，有k张卡片，每张卡片上有一个整数，卡片已经按从小到大的顺序理好。然后学姐随便报一个数x ，从卡片堆里找出第一张大于或等于x的卡片，位置为p 。 第 （p-1）%n+1 个人就要出来做游戏

Input

输入多组数据

第一行输入两个个整数n(1<=n<=100000),k(n<=k<=1000000) 表示参加活动的人数和卡片数量

第二行输入k个正整数 a1,a2,....,ak ,表示每张卡片上的数字

第三行输入一个数m (1<=m<=100000)表示询问次数

接下来m行每行输入一个整数x 表示学姐报的数

Output

输出第几个人需要出来做游戏，每个输出占一行。题目保证存在第p张卡片大于或等于 x 。

Sample Input

5? 10

2? 3? 3? 4? 5? 7? 7? 8? 9? 10

5?

3

7

9

2

10

Sample Output

2

1

4

1

5

解析：输入就是有序的，直接二分找到第一张大于或等于x位置y，打印（y-1）%n+1就ok

#include <stdio.h>
int a[1000005];
int main()
{
	int n,k,q,i,l,z,y,m;
	while(~scanf("%d%d",&n,&k)){
		for(i=1;i<=k;i++) scanf("%d",&a[i]);
		scanf("%d",&q);
		while(q--){
			scanf("%d",&l);
			z=1,y=k;
			while(z<y){//二分
				m=(z+y)>>1;
				if(a[m]>=l) y=m;
				else z=m+1;
			}
            //y就是第一个大于等于x的位置
			printf("%d\n",(y-1)%n+1);
		}	
	}
	return 0;
}