问题 M: 最亲密的x个人

时间限制: 1 Sec 内存限制: 128 MB
提交: 412 解决: 38
[提交] [状态] [命题人:jsu_admin]

题目描述

有一天，地球受到了降维打击，从三维变成了一维。从此我们都生活在一条线上，给这条线加上坐标，每个点都是大于等于 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 个人一样亲密，也需要输出）

样例输入 Copy

样例输出 Copy

定义一个结构体包含 x,id,dis dis 为到 m 的距离然后排序，按距离小的排在前面，距离相同时编号小排前

输出前 x 个人即可，再判断第 x+1 个人的距离是否和第 x 个人一样，是的话输出，反之不输出

 #include <bits/stdc++.h>

 #include<iostream>

 #include<algorithm>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 //#define DEBUG

 #define RI register int

 using namespace std;

 typedef long long ll;

 //typedef __int128 lll;

 const int N=+;

 const int MOD=1e9+;

 const double PI = acos(-1.0);

 const double EXP = 1E-;

 const int INF = 0x3f3f3f3f;

 int t,n,m,k,q;

 struct node{

     int id,x;

     bool operator <(const node &S)const{

         if(x==S.x)

             return id<S.id;

         return x<S.x;

     }

 }a[N];

 int main()

 {

     while(scanf("%d%d%d",&n,&m,&k)!=EOF){

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

             scanf("%d",&t);

             a[i].id=i;

             a[i].x=abs(t-m);

         }

         sort(a+,a+n+);

         int cnt=;

         t=;

         while(cnt<k){

             if(a[t].x!=){

                 //cnt++;

                 q=a[t].x;

                 while(q==a[t].x&&cnt<=k){

                     cout << a[t].id << endl;

                     t++;

                     cnt++;

                 }

             }else{

                 t++;

             }

         }

     }

     //cout << "Hello world!" << endl;

     return ;

 }

巴特西

问题 M: 最亲密的x个人