题面描述:

塔子哥的足球队有$n$个队员，参加了$m$次点球射门，每次射中用1表示，射失用0表示。为了评估队员的射门能力，塔子哥制定了四个排序标准：首先比较进球总数，其次比较最多一次连续进球的个数，再者比较第一次射失的顺序，最后若以上都相同，则按队员编号从小到大排序。输入包括两个整数$n$和$m$，以及每个队员的射门结果，输出队员编号按能力强弱排序。

思路

自定义排序实现。

本质就是一个自定义的实现。

• 第一关键字是每个字符串中 1 的数量，从大到小

• 第二关键字是每个字符串中最长的连续 1 的数量，从大到小

• 第三关键字：

  • 此时两个比较的串 A 和 B 中 0 的索引数量必然相同，假设数量为 k
  • 依次比较两个串中的第一个为 0 的索引，第二个为 0 的索引，... ，第 k 个为 0 的索引
  • 如果对于串 A 和串 B ，前 i 个索引均一一对应相同，第 i+1 个索引满足 indexA[i] != indexB[i]
    • 如果 indexA[i] > indexB[i] ，则 A 串为 0 的这个索引更靠后，则 A 串排序后更靠前
    • 如果 indexA[i] < indexB[i] ，则 B 串为 0 的这个索引更靠后，则 B 串排序后更靠前
    • 如果 indexA[i] = indexB[i] ，则继续比较之后的索引，如果 A 和 B 所有为 0 的索引均相同，则比较 A 和 B 的编号，即第四关键字

• 第四关键字是每个字符串的编号，从小到大

需要预处理出前两个关键字，第三关键字的比较需要至多 $O(m)$ 次，最终都相同则按编号从小到大即可。

时间复杂度：$O(nm\log n)$

具体步骤

本题的核心是根据给定的点球射门结果，对队员的射门能力进行自定义排序。我们需要定义几个关键字来实现这一排序，具体步骤如下：

1. 定义数据结构： 我们定义一个结构体 StringInfo 来存储每个队员的射门信息，主要包含以下内容：

   • index: 队员的原始编号
   • one_count: 队员进球的总数（字符串中1的数量）
   • max_con: 队员最多连续进球的次数（最长连续1的长度）
   • zeros: 队员每次射失的索引位置（字符串中0的位置列表）

2. 输入读取： 首先，读取队员的数量 n 和训练次数 m，接着逐个读取每个队员的射门结果字符串，并计算各项指标。

3. 计算指标： 对于每个队员的射门结果字符串：

   • 统计其中 1 的数量，得到 one_count。
   • 遍历字符串以计算 max_con，即最长的连续 1 的长度。
   • 同时记录每个 0 的位置，以便后续的比较。

4. 自定义排序： 使用 C++ 的 sort 函数对 StringInfo 结构体的数组进行排序，排序的优先级依次为：

   • 按照 one_count 从大到小。
   • 若 one_count 相同，则按照 max_con 从大到小。
   • 若 max_con 仍然相同，比较 zeros 列表中的索引，依次判断哪个队员在早期射失。
   • 若 zeros 也相同，则根据队员的原始编号升序排序。

5. 输出结果： 最后，将排序后的队员编号按顺序输出。

代码

Java

import java.util.*;

class StringInfo implements Comparable<StringInfo> {
    int index;          // 字符串的原始索引
    int oneCount;       // '1'的数量
    int maxCon;         // 最大连续'1'的长度
    List<Integer> zeros; // '0'的位置列表

    // 构造函数
    public StringInfo() {
        zeros = new ArrayList<>();
    }

    // 自定义排序规则
    @Override
    public int compareTo(StringInfo other) {
        if (this.oneCount != other.oneCount) 
            return Integer.compare(other.oneCount, this.oneCount);  // 按照'1'的数量降序排序
        if (this.maxCon != other.maxCon) 
            return Integer.compare(other.maxCon, this.maxCon);  // 按照连续'1'的最大长度降序排序
        for (int i = 0; i < Math.min(this.zeros.size(), other.zeros.size()); i++) {
            if (!this.zeros.get(i).equals(other.zeros.get(i))) {
                return Integer.compare(other.zeros.get(i), this.zeros.get(i));  // 按照'0'的位置列表进行排序
            }
        }
        return Integer.compare(this.index, other.index);  // 最后按照原始索引升序排序
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取n的值
        int m = scanner.nextInt();  // 读取m的值

        List<StringInfo> infos = new ArrayList<>(n);  // 存储每个字符串的信息

        for (int i = 0; i < n; ++i) {
            String s = scanner.next();  // 读取每个字符串

            StringInfo info = new StringInfo();
            info.index = i;  // 记录字符串的原始索引
            info.oneCount = 0;
            info.maxCon = 0;

            // 计算'1'的数量和'0'的位置
            for (int j = 0; j < m; ++j) {
                if (s.charAt(j) == '1') {
                    info.oneCount++;
                } else {
                    info.zeros.add(j);
                }
            }

            // 计算连续'1'的最大长度
            int j = 0;
            while (j < m) {
                if (s.charAt(j) == '0') {
                    j++;
                    continue;  // 跳过'0'
                }
                int k = j + 1;
                while (k < m && s.charAt(k) == '1') {
                    k++;
                }
                info.maxCon = Math.max(info.maxCon, k - j);  // 更新最大长度
                j = k;
            }

            infos.add(info);  // 将计算结果保存到数组中
        }

        // 对所有字符串信息进行排序
        Collections.sort(infos);

        // 输出排序后的结果
        for (StringInfo info : infos) {
            System.out.print((info.index + 1) + " ");
        }
        System.out.println();
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 定义一个结构体来封装每个字符串的相关信息
struct StringInfo {
    int index;          // 字符串的原始索引
    int one_count;      // '1'的数量
    int max_con;        // 最大连续'1'的长度
    vector<int> zeros;  // '0'的位置列表

    // 自定义排序规则
    bool operator<(const StringInfo& other) const {
        if (one_count != other.one_count) 
            return one_count > other.one_count;  // 按照'1'的数量降序排序
        if (max_con != other.max_con) 
            return max_con > other.max_con;  // 按照连续'1'的最大长度降序排序
        if (zeros != other.zeros) {
        	for(int i=0;i<zeros.size();i++){
        		if(zeros[i] < other.zeros[i]){
        			return false;
				}else if(zeros[i] > other.zeros[i]){
					return true;
				}
			}	
		}
        return index < other.index;  // 最后按照原始索引升序排序
    }
};

int main() {
    int n, m;
    cin >> n >> m;  // 读取n和m的值

    vector<StringInfo> infos(n);  // 存储每个字符串的信息

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;  // 读取每个字符串

        StringInfo info;
        info.index = i;  // 记录字符串的原始索引
        info.one_count = 0;
        info.max_con = 0;

        // 计算'1'的数量和'0'的位置
        for (int j = 0; j < m; ++j) {
            if (s[j] == '1') {
                info.one_count++;
            } else {
                info.zeros.push_back(j);
            }
        }

        // 计算连续'1'的最大长度
        int j = 0;
        while (j < m) {
            if (s[j] == '0') {
                j++;
                continue;  // 跳过'0'
            }
            int k = j + 1;
            while (k < m && s[k] == '1') {
                k++;
            }
            info.max_con = max(info.max_con, k - j);  // 更新最大长度
            j = k;
        }

        infos[i] = info;  // 将计算结果保存到数组中
    }

    // 对所有字符串信息进行排序
    sort(infos.begin(), infos.end());

    // 输出排序后的结果
    for (const auto& info : infos) {
        cout << info.index + 1 << " ";
    }
    cout << endl;

    return 0;
}

Python

n, m = map(int, input().split())
lst = input().split()

one = [0] * n
con = [0] * n
zero = [[] for _ in range(n)]

for i in range(n):
    s = lst[i]
    for j in range(m):
        if s[j] == '1':
            one[i] += 1
        else:
            zero[i].append(j)

    j = 0
    while j < m:
        if s[j] == '0':
            j += 1
            continue
        k = j + 1
        while k < m and s[k] == '1':
            k += 1
        con[i] = max(con[i], k - j)
        j = k

a = list(range(n))
a.sort(key=lambda x: (-one[x], -con[x], [-z for z in zero[x]], x))

print(*[x + 1 for x in a])

javaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    let [n, m] = (await readline()).split(" ").map(Number); // 读取 n 和 m
    let lst = (await readline()).split(" "); // 读取字符串列表

    let infos = []; // 存储每个字符串的信息

    for (let i = 0; i < n; i++) {
        let s = lst[i];

        let oneCount = 0;
        let maxCon = 0;
        let zeros = []; // 存储 '0' 的索引

        // 计算 '1' 的数量和 '0' 的索引
        for (let j = 0; j < m; j++) {
            if (s[j] === '1') {
                oneCount++;
            } else {
                zeros.push(j);
            }
        }

        // 计算最长连续 '1' 的长度
        let j = 0;
        while (j < m) {
            if (s[j] === '0') {
                j++;
                continue;
            }
            let k = j + 1;
            while (k < m && s[k] === '1') {
                k++;
            }
            maxCon = Math.max(maxCon, k - j);
            j = k;
        }

        infos.push({ index: i, oneCount, maxCon, zeros });
    }

    // 排序
    infos.sort((a, b) => {
        if (a.oneCount !== b.oneCount) return b.oneCount - a.oneCount; // '1' 的数量降序
        if (a.maxCon !== b.maxCon) return b.maxCon - a.maxCon; // 最长连续 '1' 的降序
        if (a.zeros.length !== b.zeros.length) return b.zeros.length - a.zeros.length; // '0' 数量多的排前
        for (let i = 0; i < a.zeros.length; i++) {
            if (a.zeros[i] !== b.zeros[i]) return b.zeros[i] - a.zeros[i]; // '0' 位置降序
        }
        return a.index - b.index; // 原始索引升序
    });

    console.log(infos.map(info => info.index + 1).join(" "));

    rl.close();
})();