35求调
查看原帖
35求调
1411798
LegendPei楼主2024/10/14 14:18
#include<stdio.h>
typedef struct {
    int jing, ying, tong, index;
}P;
P p[200005];
int partition(int* numbers, int left, int right, int* number)
{
    int pivot = numbers[left + (right - left) / 2];
    while (left <= right)
    {
        while (numbers[left] > pivot) left++;
        while (numbers[right] < pivot) right--;
        if (left <= right)
        {
            int temp = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = temp;
            int tem = number[left];
            number[left] = number[right];
            number[right] = tem;
            left++;
            right--;
        }
    }
    return left;
}
void quicksort(int* numbers, int left, int right, int* number)
{
    if (left < right)
    {
        int pivotIndex = partition(numbers, left, right, number);
        quicksort(numbers, left, pivotIndex - 1, number);
        quicksort(numbers, pivotIndex, right, number);
    }
}
int MIN(int a, int b, int c) {
    int min = a;
    if (b < min) {
        min = b;
    }
    if (c < min) {
        min = c;
    }
    return min;
}
int main()
{
    int n;
    scanf("%d", &n);
    int index1[n + 1], index2[n + 1], index3[n + 1], jin[n + 1], ton[n + 1], yin[n + 1];

    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &p[i + 1].jing, &p[i + 1].ying, &p[i + 1].tong);
        p[i + 1].index = i + 1;
        index1[i + 1] = i + 1;
        index3[i + 1] = i + 1;
        index2[i + 1] = i + 1;
        jin[i + 1] = p[i + 1].jing;
        yin[i + 1] = p[i + 1].ying;
        ton[i + 1] = p[i + 1].tong;
    }
    quicksort(jin, 1, n, index1);
    quicksort(yin, 1, n, index2);
    quicksort(ton, 1, n, index3);
    int index11[n + 1], index22[n + 1], index33[n + 1];
    for (int i = 1; i < n + 1; i++)
    {
        int a = 0, b = 0, c = 0;
        if (i > 1 && jin[i] == jin[i - 1]) {
            a++;
            index11[p[index1[i]].index] = i - a;
        }
        else {
            index11[p[index1[i]].index] = i;
            a = 0;
        }
        if (i > 1 && yin[i] == yin[i - 1]) {
            b++;
            index22[p[index2[i]].index] = i - b;
        }
        else {
            index22[p[index2[i]].index] = i;
            b = 0;
        }
        if (i > 1 && ton[i] == ton[i - 1]) {
            c++;
            index33[p[index3[i]].index] = i - c;
        }
        else {
            index33[p[index3[i]].index] = i;
            c = 0;
        }
    }
    for (int i = 1; i < n + 1; i++) {
        printf("%d\n", MIN(index11[i], index22[i], index33[i]));
    }

    return 0;
}

p[].index代表原始序列,p[].jing是金牌数,经过quicksort后jin是降序排序后的p[].jing,然后index1代表排序后小朋友的位置,index11代表排位(剩下同理)

比如输入样例 4 8 5 0 4 5 3 4 1 2 2 1 1 他们的index11,index22,index33分别为 1 1 4 2 1 1 2 3 2 4 3 3

然后输出最小的那个

2024/10/14 14:18
加载中...