2 solutions

  • 0
    @ 2024-8-26 11:47:01 
    #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
using namespace std;

struct Info
{
    int id;
    vector<int> vec;
    int max;
    int scores;
};

int getMaxSubArray(string str)
{
    int maxCount = 0;  // 记录最大连续 '1' 的数量
    int currentCount = 0;  // 当前连续 '1' 的数量

    for (char c : str) {
        if (c == '1') {
            currentCount++;  // 如果是 '1'，增加当前计数
        } else {
            maxCount = std::max(maxCount, currentCount);  // 更新最大值
            currentCount = 0;  // 重置当前计数
        }
    }

    // 最后一次检查，防止字符串以 '1' 结尾未更新最大值
    maxCount = std::max(maxCount, currentCount);

    return maxCount;
}

vector<int> getMaxSubArray2(string str)
{
    vector<int> pairvec;
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == '0')
        {
            pairvec.push_back(i);
        }
    }
    return pairvec;
}

bool getmax(vector<int> a, vector<int> b)
{
    for(int i = 0; i < a.size(); i++)
    {
        if(a[i] == b[i])  continue;
        if(a[i] > b[i]) return true;
        else return false;
    }
    return false;
}

bool isequal(vector<int> a, vector<int> b)
{
    for(int i = 0; i < a.size(); i++)
    {
        if(a[i] != b[i]) return false;  
    }
    return true;
}

int getoneNums(string str)
{
    int res = 0;
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == '1')
        {
            res++;
        }
    }
    return res;
}

int main()
{
    int peoples,trains;
    cin >> peoples >> trains;
    getchar();
    string line;
    getline(cin, line);
    istringstream is(line);
    string str;
    vector<Info> infos;
    int i = 0;
    while(getline(is, str,' '))
    {
        Info info;
        info.id = i;
        info.scores = getoneNums(str);
        vector<int> tmp = getMaxSubArray2(str);
        info.vec = tmp;
        info.max = getMaxSubArray(str);
        infos.push_back(info);
        i++;
    }
    sort(infos.begin(), infos.end(), [](Info a, Info b){
        if(a.scores != b.scores) return a.scores > b.scores;
        if(a.max != b.max) return a.max > b.max;
        if(!isequal(a.vec, b.vec)) return getmax(a.vec, b.vec);
        return a.id < b.id;
    });
    for(auto info : infos)
    {
        cout << info.id + 1 << " ";
    }
    return 0;
}
    • 0
      @ 2024-8-21 4:32:47

      题面描述:

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

      思路

      自定义排序实现。

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

      • 第一关键字是每个字符串中 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(m) 次，最终都相同则按编号从小到大即可。

      时间复杂度：O(nmlog⁡n)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])
      • 1

      2024.04.24-暑期实习-第二题-塔子哥的足球队

      Information

      ID
      90
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      5
      Tags
      # Submissions
      158
      Accepted
      43
      Uploaded By
      1. About
      2. Contact Us
      3. Privacy
      4. Terms of Service
      5. Copyright Complaint
      6. Language
      7. Legacy mode
      8. Theme
      2. 湘ICP备2023007293号
      3. Worker 0, 26ms
      4. Powered by Hydro v4.14.1 Community