2022 group programming ladder race L2-1 inserting pine branches

L2-1 pine branch insertion

Workers in artificial pine branch processing plant need to insert plastic pine needles of various sizes into pine branches to make large and small pine branches. Their workflow is (not) like this:

  • Each person has a small box at hand, and the initial state is empty.
  • There are endless pine branches and a pusher in front of everyone, pushing a random type of pine needle each time.
  • First, the worker picks up an empty pine branch and finds the top pine needle from the small box - if the small box is empty, take a pine needle from the pusher. Insert this pine needle into the bottom of the branch.
  • When inserting the pine needle in the back, workers need to ensure that the pine needle inserted into a non empty pine branch at each step cannot be larger than the pine needle inserted in the previous step. If the top pine needle in the small box meets the requirements, take it and insert it; Otherwise, take one from the pusher. If what you get from the pusher still doesn't meet the requirements, stack it in a small box and continue to take one from the pusher. Note that it is assumed that the pine needles in the small box are stacked in the order in which they are put in, and the worker can only take out the top one (i.e. the last one) at a time.
  • When one of the following three situations occurs, the worker will end the pine branch production and start the next one:

(1) The small box is full, but the pine needle taken from the pusher still doesn't meet the requirements. At this time, put the pine branch in your hand into the finished product basket, press the pine needle taken from the pusher back to the pusher, and start the production of the next pine branch.

(2) The top pine needle in the small box does not meet the requirements, but there is no pine needle on the pusher. At this time, put the pine branch in your hand into the finished basket and start the production of the next pine branch.

(3) The pine branch in your hand is full of pine needles. Put it into the finished basket and start the production of the next pine branch.

N ow, given the size of the # pine needles sequentially transmitted from the pusher and the capacity of the small box and pine branches, please write a program to automatically list the information of each finished pine branch.

Input format:

Input: three positive integers are given in the first line: N (≤ 103), which is the number of loose needles on the pusher; M (≤ 20) is the maximum number of pine needles that can be stored in a small box; K (≤ 5) is the maximum number of pine needles that can be inserted into a pine branch.

The next line gives N ^ positive integers not exceeding ^ 100 ^ which is the size of pine needle sheets pushed out sequentially on the pusher.

Output format:

The information of each pine branch finished product occupies one line, and the order is the size of each pine needle from bottom to top. The numbers shall be separated by one space, and there shall be no extra space at the beginning and end of the line.

Idea:

You will find that the two red circles have the same idea, expressed by a function solve, but n is slightly different, expressed by the mark n1;

As for whether the pine branch is 0, the inhang function output indicates that the time complexity is n, and the time complexity of adding the box can be ignored, because the box can not be put into the heap; The following is the code of 25 points. For the first time, l2 only wrote this question and only got 19 points. Continue to refuel and come back next year.

#include<bits/stdc++.h>
using namespace std;
stack<int>he;
queue<int> tui;
vector<vector<int>> hang(1007);
int n, m, k;//n tui pine branch, m he maximum; k is the maximum;
int t=0, flag = 0,temp,bflag=0,know=0;//
int  solve(int n1);//Return 1 to end n1=1 indicates that the box is empty and else is not empty
int  inhang(int n2);//n2 1 box kong 2 boxes are not empty --- return 1 with pine branches 0 without pine branches
int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		tui.push(temp);
	}
	while (1) {
		flag = 0;
		   bflag = 0;
		if(he.empty()){
			bflag = solve(1);
		}
		else {
			if (inhang(2)) {
				int nosize = hang[t].size();
				if (he.top() <= hang[t][nosize - 1]) {
					hang[t].push_back(he.top());
					he.pop();
					know++;
				}
				else
				bflag=solve(0);
			}
		}
		if (bflag == 1) break;
		if (know == k||flag==1) {
			t++;
			know = 0;
		}
	}
	if (hang[t].size() == 0) t--;
	for (int i = 0; i <= t; i++) {
		for (int j = 0; j < hang[i].size();j++) {
			if (j != 0) printf(" ");
			printf("%d", hang[i][j]);
		}
		if (i != t) cout << endl;
	}
	return 0;
}
int  inhang(int n2) {
	int iflag = 0;
	if (hang[t].size() == 0) {
		if (n2 == 1) {
			hang[t].push_back(tui.front());
			tui.pop();
		}
		else {
			hang[t].push_back(he.top());
			he.pop();

		}
		know++;
	}
	else iflag = 1;
	return iflag;
}
int solve(int n1) {
	if (!tui.empty()) {//Not empty
		if (inhang(1)) {//know>0;
			int nowsize = hang[t].size();
			while (1) {
				if (tui.empty()) {
					flag = 1;
					break;
				}
				if (tui.front() <= hang[t][nowsize - 1]) {//accord with
					hang[t].push_back(tui.front());
					tui.pop();
					know++;
					break;
				}
				else if (he.size() == m) {
					flag = 1;//he man
					break;
				}
				else {//Put tui into he
					he.push(tui.front());
					tui.pop();
				}
			}
		}
		return 0;
	}
	else {
		if (n1 == 1) {
			return 1;
		}
		else {
			flag = 1;
			return 0;
		}
	}
}

 

 

 

 

Tags: C C++ Algorithm data structure

Posted by explorer on Thu, 28 Apr 2022 09:10:42 +0300