题目链接:http://120.78.162.102/problem.php?id=6251
时间限制: 1 Sec  内存限制: 128 MB

题目描述

有一天，地球受到了降维打击，从三维变成了一维。从此我们都生活在一条线上，给这条线加上坐标，每个点都是大于等于 0 的正整数。
有一天小明突发奇想，想知道谁是他最亲密的人，距离小明越近的人和小明越亲密。
假设有 N 个人，每个人的编号为 i（1 <= i <= N ），坐标为 ki（k[i-1] <= k[i] <= k[i+1]），小明的坐标为 M（小明是 N 个人中的一个），你们可以帮助小明找到他最亲密的 X个人的编号吗？

输入

多组输入
对于每组数据，第一行为三个整数N（0<N<=100000 ）、M（0<M<=100000000）、X（X <= N && X <= 100）
第二行有N个数，分别表示 N 个人的坐标

输出

小明最亲密的 X 个人的编号（亲密度相同的，按id从小到大输出。如果第 x+1 个人和第 x 个人一样亲密，也需要输出）

样例输入

3 2 1
1 2 4
3 2 1
1 2 3

样例输出

1
1
3

解题思路

类似于两个有序数组的合并。我们可以先定义两个变量，一个向前找，一个向后找。然后比较一下，哪个离m比较近，哪个的编号就存进数组，当两个数离m一样近的时候，编号都存进数组。

#include <stdio.h>
#define N 100010
int a[N], s[N];
int main()
{
    int n, m, x, k, i, j;
    while (~scanf("%d%d%d", &n, &m, &x))
    {
        for (i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            if (a[i] == m)
                k = i;
        }
        i = k - 1;
        j = k + 1;
        k = 0;
        while (i >= 0 && j < n && k < x)
        {
            if (m - a[i] < a[j] - m)
                s[k++] = i--;
            else if (m - a[i] > a[j] - m)
                s[k++] = j++;
            else
            {
                s[k++] = i--;
                s[k++] = j++;
            }
        }
        while (i >= 0 && k < x)
            s[k++] = i--;
        while (j < n && k < x)
            s[k++] = j++;
        for (i = 0; i < k; i++)
            printf("%d\n", s[i] + 1);
    }
    return 0;
}