CCF CSP 201909-1.小明种苹果

样例1输入

3 3
73 -8 -6 -4
76 -5 -10 -8
80 -6 -15 0

样例1输出

167 2 23

样例2输入

2 2
10 -3 -1
15 -4 0

样例2输出

17 1 4

---

分析

本题考察排序算法，关键在于求k值，即疏果个数最多的苹果树编号。

按照如下方式，对所有的苹果树进行排序：

1.按照疏果操作去掉的苹果个数降序排列；

2.当疏果操作去掉的苹果个数相等时，则按照苹果树的编号升序排列。

排序完成后，第一棵苹果树的编号即为所求的k值。

• C/C++语言

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct Apple
{
    int no;
    int origin_count;
    int drop_count;
} Apple;

int cmp(const void *a, const void *b)
{
    Apple *x = (Apple *)a;
    Apple *y = (Apple *)b;
    if (x->drop_count != y->drop_count)
    {
        return y->drop_count - x->drop_count;
    }
    return x->no - y->no;
}

int main(int argc, char const *argv[])
{
    int n, m;
    scanf("%d %d", &n, &m);

    int i, j, t = 0;
    int aj;
    Apple apple[n];

    for (i = 0; i < n; i++)
    {
        apple[i].no = i + 1;
        apple[i].drop_count = 0;
        scanf("%d", &apple[i].origin_count);

        for (j = 0; j < m; j++)
        {
            scanf("%d", &aj);
            apple[i].drop_count += aj;
        }
        apple[i].drop_count = -apple[i].drop_count;

        t += apple[i].origin_count - apple[i].drop_count;
    }

    qsort(apple, n, sizeof(Apple), cmp);
    printf("%d %d %d\n", t, apple[0].no, apple[0].drop_count);
    return 0;
}

• Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();

        Apple[] apples = new Apple[n];
        int t = 0;
        for (int i = 0; i < n; i++) {
            int a0 = scan.nextInt();

            int dropCount = 0;
            for (int j = 0; j < m; j++) {
                dropCount += scan.nextInt();
            }
            dropCount = -dropCount;
            apples[i] = new Apple(i + 1, dropCount);

            t += a0 - dropCount;
        }
        scan.close();

        Arrays.sort(apples, (a, b) -> {
            if (a.dropCount != b.dropCount) {
                return b.dropCount - a.dropCount;
            }
            return a.no - b.no;
        });

        System.out.printf("%d %d %d\n", t, apples[0].no, apples[0].dropCount);
    }

    static class Apple {
        int no;
        int dropCount;

        public Apple(int no, int dropCount) {
            this.no = no;
            this.dropCount = dropCount;
        }
    }
}

• Python

def main():
    n, m = map(int, input().split(' '))

    t = 0
    apples = []
    for i in range(1, n + 1):
        arr = list(map(int, input().split(' ')))
        drop_count = -sum(arr[1:])
        apples.append([i, drop_count])
        t += arr[0] - drop_count;
    
    res = sorted(apples, key=lambda x: (x[1], -x[0]), reverse=True)[0]
    print('%d %d %d' % (t, res[0], res[1]))


if __name__ == '__main__':
    main()