题目解析
给定盒子大小和松枝干上最大的松针片数量
求出按照题意所求得得松针信息
解题思路
先读题
松枝干上插入松枝片的顺序
- 一定是先从盒子中取 然后再是推送器上的
松枝干上可以插入松针片
- 当前松枝干上没有松针片
- 当前要插入的松针片 一定不能比 松枝干最上面的 大
松针片放入盒中
- 当前推送器上的松针片 不满足 小于等于 松枝干最上面的
那些样子的松枝干算完成的
- 盒子已经满了， 且当前推送器上的松针片不能插入
- 盒子最上面的不能插入， 且推送器上没有松针片了
- 当前松枝干 已经插满 松针片了
其实这个只是一个读题的题目的模拟 (就是题目又臭又长 掌握小细节的模拟)
可以去队列存储推送器上的松针片 用栈存储盒子中的松针片 用list存储松枝干
大致流程图如下
做了好久一直wa在下面这个样例
输入
8 3 4
20 25 28 27 28 26 25 25 25
输出
20
27 26 25 25
28 28 25
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int inf = 0x3f3f3f3f;
// 存储松枝干
static ArrayList<Integer> sz = new ArrayList<Integer>();
// 输出松枝干
static void printlist()
{
for (int i = 0; i < sz.size(); i++)
{
if (i != 0)
out.print(" ");
out.print(sz.get(i));
}
out.println();
sz.clear();
}
public static void main(String[] args)
{
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
// 存储推送器上的松针片
LinkedList<Integer> ts = new LinkedList<Integer>();
for (int i = 1; i <= n; i++)
{
int x = sc.nextInt();
ts.addLast(x);
}
// 存储盒子中的松针片
Stack<Integer> box = new Stack<Integer>();
while (ts.size() != 0 || box.size() != 0)
{
// 记录当前松枝干上的最上面一个
int now = inf;
if (sz.size() != 0)
now = sz.get(sz.size() - 1);
// 如果盒子中不为空 且 盒子中的最上面能插入 那么就将其插入
if (box.size() != 0 && box.peek() <= now)
sz.add(box.pop());
else
{
// 如果当前推送器上的松针片不为空 且能插入 就将其插入
if (ts.size() != 0 && ts.peekFirst() <= now)
sz.add(ts.pollFirst());
// 如果当前推送器上的松针片不为空 且 盒子中的松针片小于m 那么就能将松针片放入盒子中
else if (ts.size() != 0 && box.size() < m)
box.add(ts.pollFirst());
// 否则就是盒子满了 不能再次放下了
else
printlist();
}
// 如果松枝干插满了 那么就输出当前的松枝干
// 为什么盒子满了不在这里输出呢
// 因为他只是盒子中满了 但是他还是可以 将推送器上的 插入
if (sz.size() == k)
printlist();
}
// 输出最后的松枝干
// 因为会到最后没有插满松针的情况 但是盒子中和推送器上都没有松针片了
if (sz.size() != 0)
printlist();
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}