141. 最後的元素

 avatar
user_6817964
c_cpp
2 years ago
1.2 kB
1
Indexable
Never
#include <stdio.h>
#include <stdlib.h>

int extractMax(int* stone, int stoneSize);
int lastStoneWeight(int* stones, int stonesSize);

int extractMax(int* stone, int stoneSize) {
    int max = stone[0], index = 0;
    for (int i = 1; i < stoneSize; i++) {
        if (stone[i] > max) {
            max = stone[i];
            index = i;
        }
    }
    return index;
}


int lastStoneWeight(int* stones, int stonesSize) {
    int y, x, y_index, x_index;
    while (1)
    {
        y_index = extractMax(stones, stonesSize);

        if (stones[y_index] == -1) {
            return 0;
        }

        y = stones[y_index];
        stones[y_index] = -1;


        x_index = extractMax(stones, stonesSize);

        if (stones[x_index] == -1) {
            return y;
        }

        x = stones[x_index];
        stones[x_index] = -1;

        if (x != y) {
            stones[y_index] = y - x;
        }
    }
}

int main() {
    int n = 0;
    int ans;
    scanf("%d", &n);
    int* a = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    ans = lastStoneWeight(a, n);
    printf("%d", ans);
    free(a);
    return 0;
}