2023.05.31-暑期实习-第一题-塔子哥的数据

Kaf_sta LV 4 @ 7 months ago

def print_sorted_list(sorted_list, n):
    cnt = 0
    for batch in sorted_list:
        for i in range(batch[0]):
            print(batch[1], end='')
            cnt += 1
            if cnt >= n:
                return


n, m = map(int, input().strip().split())
lines = []

for i in range(m):
    lines.append(list(map(int, input().strip().split())))
    lines_sorted = sorted(lines, key=lambda x: -x[1])
    print_sorted_list(lines_sorted, n)
    print()

wangxuehui LV 9 @ 7 months ago

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    priority_queue<pair<int, int>> q;
    for (int i = 0; i < m; i++)
    {
        int a,b;
        cin >> a>> b;
        q.emplace(b,a); //以正整数最大排序
        int sum = n;
        string s;
        auto q1=q;
        while (!q1.empty())
        {
            auto a= q1.top();
            q1.pop();
            int val =a.first;
            int num =a.second;
            if (sum == 0) break;
            else if (num < sum)
            {
                sum -= num;
                for (int j = 0; j < num; j++)
                    s += to_string(val);
            }
            else
            {
                for (int j = 0; j < sum; j++)
                    s +=to_string(val);
                sum=0;
            }
        }
        cout<<s<<endl;
    }
}

zqq_noLay LV 4 @ 8 months ago

小根堆的方法

思路：只维护大小为N的小根堆，输入一批新数据的时候把最小元素（堆顶元素）pop出去。

问题：需要加入一些剪枝判断的处理，否则会TLE

#include<bits/stdc++.h>
using namespace std;

string getRes(priority_queue<int, vector<int>, greater<int>>& minHeap) {
    int n = minHeap.size();
    string res = {};
    string tmp;
    priority_queue<int, vector<int>, greater<int>> tmp_que = minHeap;
    for (int i = 0; i < n ; i++) {
        tmp = to_string(tmp_que.top());
        res = tmp + res;
        tmp_que.pop();    // 顶端是小的，随着遍历越来越大，填充在前面
    }
    return res;
}


int main() {
    int n, m;
    cin >> n;    // 保留个数
    cin >> m;    // 输入数据行数

    int A, B;
    string res = {};    // 结果要求是字符串
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int min = 0;
    for (int i = 0; i < m; i++) {
        cin >> A;    // 数量
        cin >> B;    // 数字
        if (B > min) {
            if (!minHeap.empty())min = minHeap.top();

            for (int j = 0; j < A; j++) {
                minHeap.push(B);    // 先加进来
                if (minHeap.size() > n) minHeap.pop();    // 把小的弹出去
                if (j > n) break;    // 剪枝————应对一次输入非常多数据的情况
            }
        };

        res = getRes(minHeap);

        // 每输入一行  就输出一行
        cout << res << endl;
    }
    return 0;
}

TaZi SU @ 9 months ago

思路：大根堆+模拟

给定 $M$ 个数据，每个数据为 $A$ 个重复的 $B$ 。要求每读入一次数据，最多输出当前已读数据中最大的 $N$ 个值。

为了能够快速得到最大的值，我们可以使用大根堆来对数据进行存储。

什么是大根堆？

其学名是优先队列。具体表现形式(或者说我们自己手动模拟的形式)是一颗二叉树，每个结点最多有两个儿子，且对于任意一个结点，都符合：该结点任意儿子的值，都比该结点的值小。因此，堆顶(或者说二叉树的根节点)就是所有数中最大的值。

对于C++选手来说，刚好有STL能够使用，即priority_queue，其默认是大根堆。比较基础的几个函数分别是：

pop()，弹出堆顶，并返回该元素
push(x)，将 $x$ 加入到堆中
size()，返回堆中当前元素的个数
clear()，清空堆

其他语言也有相应的封装包，比如python里有heapq。因此如果自己不想动手实现一个优先队列的话，可以直接使用封装包。

由于该题的数据量很小，我们可以直接借助大根堆来模拟这个过程。

具体过程如下：

读入一行数据，将其加入到大根堆q中
从大根堆不断取出堆顶，进行输出，并将该数据放入到临时队列tmp中，直到输出一共 $N$ 个数字
将tmp中的数据再重新放回堆中

由于 $N$ 很小，最大仅为24，也就是说每次最多输出24个字符，而堆的每次操作都可以近似看作 $O(logM)$ 的，最坏情况下每次取出堆中24个数据(每个数据只重复1次)输出再放回去也就是 $O(NlogM)$ 的时间复杂度。读入 $M$ 行数据，总共要输出 $M$ 次，因此总时间复杂度为 $O(NMlogM)$ 。

代码

C++

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int n,m;

struct node{
	int cnt;// 重复多少次 
	int val;// 值 
};

queue<node> tmp;
priority_queue<node> q;

bool operator <(const node a,const node b){// 重载运算符 
	return a.val<b.val;
}

int main(){
	scanf("%d %d",&n,&m);
	node a;
	for(int i=1,rest;i<=m;++i){
		scanf("%d %d",&a.cnt,&a.val);
		q.push(a);
		rest=n;// rest为输出某一字符后，剩余的长度，初始为n 
		while(rest>0){
			if(!q.size()) break;// 大根堆里已经没有字符了，直接break 
			// 取出堆顶 
			a=q.top();
			q.pop();
			// 输出 min(rest,a.cnt) 次 
			for(int i=1;i<=min(rest,a.cnt);++i){
				printf("%d",a.val);
			}
			// 从堆里取出来放到临时队列中 
			tmp.push(a);
			rest-=a.cnt;
		}
		while(tmp.size()){// 将队列中的数据重新放回堆中 
			q.push(tmp.front());
			tmp.pop();
		}
		printf("\n");
	}
	
	
	return 0;
}

python

import heapq

class Node:
    def __init__(self, cnt, val):
        self.cnt = cnt
        self.val = val
    
    def __lt__(self, other):
        return self.val < other.val

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

q = []
tmp = []

for _ in range(m):
    cnt, val = map(int, input().split())
    heapq.heappush(q, Node(cnt, val))
    rest = n  # rest为输出某一字符后，剩余的长度，初始为n
    while rest > 0:
        if not q:
            break  # 大根堆里已经没有字符了，直接break
        # 取出堆顶
        a = heapq.heappop(q)
        # 输出 min(rest,a.cnt) 次
        for _ in range(min(rest, a.cnt)):
            print(a.val, end="")
        # 从堆里取出来放到临时队列中
        tmp.append(a)
        rest -= a.cnt
    while tmp:
        # 将队列中的数据重新放回堆中
        heapq.heappush(q, tmp.pop(0))
    print()

Java

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Main {
    static class Node implements Comparable<Node> {
        int cnt; // 重复多少次
        int val; // 值

        public Node(int cnt, int val) {
            this.cnt = cnt;
            this.val = val;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.val, other.val);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Queue<Node> q = new PriorityQueue<>();
        Queue<Node> tmp = new PriorityQueue<>();

        for (int i = 0; i < m; i++) {
            int cnt = scanner.nextInt();
            int val = scanner.nextInt();
            q.offer(new Node(cnt, val));
            int rest = n; // rest为输出某一字符后，剩余的长度，初始为n
            while (rest > 0) {
                if (q.isEmpty()) break; // 大根堆里已经没有字符了，直接break
                // 取出堆顶
                Node a = q.poll();
                // 输出 min(rest,a.cnt) 次
                for (int j = 0; j < Math.min(rest, a.cnt); j++) {
                    System.out.print(a.val);
                }
                // 从堆里取出来放到临时队列中
                tmp.offer(a);
                rest -= a.cnt;
            }
            while (!tmp.isEmpty()) {
                // 将队列中的数据重新放回堆中
                q.offer(tmp.poll());
            }
            System.out.println();
        }
    }
}

Go

package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	cnt int // 重复多少次
	val int // 值
}

type PriorityQueue []Node

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].val < pq[j].val
}
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(Node)
	*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	q := make(PriorityQueue, 0)
	tmp := make(PriorityQueue, 0)

	for i := 0; i < m; i++ {
		var a Node
		fmt.Scan(&a.cnt, &a.val)
		heap.Push(&q, a)
		rest := n // rest为输出某一字符后，剩余的长度，初始为n
		for rest > 0 {
			if len(q) == 0 {
				break // 大根堆里已经没有字符了，直接break
			}
			// 取出堆顶
			a := heap.Pop(&q).(Node)
			// 输出 min(rest,a.cnt) 次
			for j := 0; j < min(rest, a.cnt); j++ {
				fmt.Print(a.val)
			}
			// 从堆里取出来放到临时队列中
			heap.Push(&tmp, a)
			rest -= a.cnt
		}
		for len(tmp) > 0 {
			// 将队列中的数据重新放回堆中
			heap.Push(&q, heap.Pop(&tmp).(Node))
		}
		fmt.Println()
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Js

const readline = require('readline');

function min(a, b) {
  return a < b ? a : b;
}

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let n, m;
const q = [];
const tmp = [];

rl.on('line', (line) => {
  const input = line.split(' ').map(Number);
  if (!n) {
    [n, m] = input;
    return;
  }
  const [cnt, val] = input;
  q.push({ cnt, val });
  let rest = n; // rest为输出某一字符后，剩余的长度，初始为n
  while (rest > 0) {
    if (q.length === 0) break; // 大根堆里已经没有字符了，直接break
    // 取出堆顶
    const a = q.shift();
    // 输出 min(rest,a.cnt) 次
    for (let i = 0; i < min(rest, a.cnt); i++) {
      process.stdout.write(String(a.val));
    }
    // 从堆里取出来放到临时队列中
    tmp.push(a);
    rest -= a.cnt;
  }
  while (tmp.length > 0) {
    // 将队列中的数据重新放回堆中
    q.push(tmp.shift());
  }
  process.stdout.write('\n');
});

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

# Submissions

156

Accepted

Uploaded By

TaZi

4 solutions

思路：大根堆+模拟

代码

C++

python

Java

Go

Js

Information

Status

Development

Support