【9210】找礼物（char* num[2000]的使用 get char num[i] = new char[1000]）

Time Limit: 10 second

Memory Limit: 2 MB

问题描述

新年到了，突然间，就在那美丽的一霎那，你好友和你（K个人）的周围满是礼物，你发扬你帅气的风格，让你的好友先拿，但是每个人只能拿当前离自己最近的礼物[当然如果有并列的多个礼物离你的距离相等（精确到小数后四位,所有运算均为去尾），这些礼物就都属于这个人]。现在你们所在的位置是原点(0,0)，每个礼物的位置用坐标表示。现在告诉你每个礼物的坐标，还有每个礼物是谁送的。要你找出你的礼物离你多远，你能拿到多少礼物，这些礼物是谁送的。如果你拿不到礼物，请输出“555…”

Input

第一行：N 和 K 分别表示礼物的个数和人数。

第二到N+1行：每行先是赠送礼品人的姓名，然后是礼物的坐标（x,y）。

数据间空格分割

Output

第一行： D 和 U 表示礼物距你多远（只要去尾后的整数）和你能拿到多少礼物。

第二到U+1行：每行一个人名，表示送礼的人。<按照输入的顺序输出>

Sample Input

10 2

Pos 18426 3429

Kill -28989 -12602

WGPO -6095 11806

EhiEN 4 -3

DICV 7752 -27723

FBI 15713 -24074

QOHR -3194 -30639

WWJ 3 4

GKIX -5 0

CB 0 2

Sample Output

5 3

EhiEN

WWJ

GKIX

【题解】

保留4位的方法是 floor( sqrt(x*x + y*y) * 10000)/10000；存入数组中，以距离为关键字进行升序排。然后先给其他的小伙伴分，最后剩下自己的，在输入数据的时候记录每个礼物出现的先后顺序，最后输出的时候对自己要输出的礼物按照出现的顺序再排一次序。最后输出就好。这里的double类可以直接用“==”判断两个数是否相等。前面输入字符串的时候，用了char* name[90000] 这个东西，在输入之前要getchar一下，然后是num[i] = new char[1000],之后就能用scanf("%s")来进行输入了，会遇到空格停止。所以可以直接一排输入scanf("%s%lf%lf")，当然这是从别人那里挖过来的。用cin会超时。

【代码】

#include <cstdio>

#include <iostream>

#include <string>

#include <cmath>

#include <stdlib.h>

using namespace std;

struct data

{

    double dis;

    int first;

};

int n,k;

data a[90000];

char* name[90000]; //要记住这个输入字符串的写法

void input_data()

{

    scanf("%d %d",&n,&k);

    int m = 0;

    getchar(); //在用之前要先getchar一下。

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

        {

            name[i] = new char[1000]; //记住 new char [长度]

            double x,y;

            scanf("%s%lf%lf",name[i],&x,&y); //就可以直接用“%s"来进行输入了

            a[i].dis = floor( sqrt(x*x + y*y) * 10000)/10000; //floor是取整函数

            a[i].first = ++m; //记录下每个礼物出现的先后顺序

        }

}

void kp(int l,int r) //以距离为关键字进行从小到大排

{

    int i = l,j = r;

    double m = a[(i+j)/2].dis;

    do

    {

        while (a[i].dis < m) i++;

        while (m < a[j].dis) j--;

        if (i <= j)

            {

                a[0] = a[i];a[i] = a[j];a[j] = a[0]; //与之相关的所有东西 都要进行变换

                name[0] = name[i];name[i] = name[j];name[j] = name[0];

                i++;j--;

            }

    }

    while (i <= j);

    if (l < j) kp(l,j);

    if (i < r) kp(i,r);

}

void kp2(int l,int r) //以出现的先后顺序为关键字 进行从小到大排序

{

    int i = l,j = r,m = a[(i+j)/2].first;

    do

    {

        while (a[i].first < m) i++;

        while (m < a[j].first) j--;

        if (i <= j)

            {

                a[0] = a[i];a[i] = a[j];a[j] =a[0];

                name[0] = name[i];name[i] = name[j];name[j] = name[0];

                i++;j--;

            }

    }

    while (i <=j );

    if (l < j) kp2(l,j);

    if (i < r) kp2(i,r);

}

void get_ans()

{

    k--; //k包括自己 我们先减去自己 处理其他人

    kp(1,n);

    int i = 1;

    while (k > 0 && i <= n) //先过滤掉别人的礼物

        {

            int j = i+1;

            while ( a[j].dis == a[i].dis) j++;

            i = j;

            k--;

        }

    if (k > 0) //如果别人都没分完则自己不可能有剩余礼物。但是好像有问题。。。如果别人刚好分完了呢？我在下面加几行。

        {

                printf("555…");

                return;

        }

    if (k == 0 && i > n)

        {

            printf("555…");

            return;

        }

    int j = i+1;

    while ( a[j].dis == a[i].dis) j++;//然后找哪些礼物是自己的。

    int dd = int(a[i].dis); //直接取整就好

    printf("%d %d\n",dd,j-i);

    kp2(i,j-1); //对自己的礼物以出现的先后顺序进行排序。

    for (int kk = i;kk <=j-1;kk++)

        printf("%s\n",name[kk]);

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    input_data();

    get_ans();

    return 0;

}

巴特西

【9210】找礼物（char* num[2000]的使用 get char num[i] = new char[1000]）

Input

Output

Sample Input

Sample Output

最新文章

热门文章