题目链接

星际舰队的补给分配

题目描述

一支星际舰队需要进行能量分配。补给舰队列 按顺序提供能量，作战舰队列 按顺序接收能量。整个流程遵循一套特定的分配规则，直到补给舰用完或作战舰全部满足需求。任务是计算最终有多少艘作战舰未能获得补给。

设当前补给舰的能量为 ，作战舰队列队首的需求为 。 分配规则如下：

  1. 精准匹配 ()：补给舰的能量刚好满足队首作战舰。两者都出队。
  2. 超量分配 ()：补给舰的能量超额。寻找一个最大的 ，使得队首 艘作战舰的总需求 。这 艘作战舰和该补给舰都出队。
  3. 需求不足 ()：补给舰能量不足。队首作战舰放弃本次机会，移动到队列末尾。该补给舰继续尝试为新的队首作战舰进行补给。

输入:

  • 第一行：补给舰队列 中各舰的能量值。
  • 第二行：作战舰队列 中各舰的需求量。

输出:

  • 一个整数，代表最终未能获得补给的作战舰数量。

解题思路

这是一个纯粹的模拟问题。我们需要按照题目描述的规则，一步一步地处理两个队列的交互。

数据结构选择

题目明确描述了“队列”的先进先出（FIFO）特性，并且规则3要求能将队首元素移到队尾。因此，双端队列（deque）是实现这个逻辑最理想的数据结构。它支持高效地从队首移除元素和在队尾添加元素。

模拟流程

我们可以设计一个主循环，只要补给队列和作战队列都非空，就持续进行分配。

  1. 外层循环：每次循环，从补给队列中取出一艘补给舰，设其能量为 。
  2. 内层逻辑（处理同一艘补给舰）：这艘能量为 的补给舰需要与作战队列进行交互，直到它的能量被用掉，或者它无法满足任何一艘作战舰的需求为止。
    • 处理“需求不足”的循环：规则3是整个模拟的核心难点。一艘补给舰可能会因为连续遇到需求过大的作战舰，而导致作战队列无限循环。我们需要识别这种情况。
      • 一个有效的办法是设置一个尝试计数器 attempts。在一艘补给舰的“回合”开始时，记录当前作战队列的长度 max_attempts。如果这艘补给舰连续尝试了 max_attempts 次都因为“需求不足”而失败，就意味着队列里的每一艘作战舰它都满足不了。此时，这艘补给舰的能量就浪费了，我们应该跳出内层逻辑，处理下一艘补给舰。
    • 处理“精准匹配”和“超量分配”：
      • 一旦遇到 的情况，就执行相应的规则。
      • 在“超量分配”中，我们需要从队首开始累加需求，找到满足条件的最大舰船数 ，然后将这 艘作战舰移出队列。
      • 一旦能量分配完成（规则1或2），当前补给舰的任务就结束了，我们应该结束内层逻辑，返回外层循环去取下一艘补给舰。

算法总结

  1. 将输入的两行数字分别存入两个双端队列：supply_q 和 demand_q。
  2. 当 supply_q 和 demand_q 都不为空时，执行循环： a. 从 supply_q 队首取出一个能量值 。 b. 初始化 attempts = 0，并记录 max_attempts = demand_q.size()。 c. 进入一个子循环，条件是 attempts < max_attempts 并且 demand_q 不为空： i. 获取队首作战舰需求 。 ii. 如果 ：将队首作战舰移到队尾，attempts 加一。 iii. 如果 ：执行精准匹配或超量分配的逻辑，移除相应数量的作战舰。然后跳出子循环。
  3. 主循环结束后，demand_q 中剩余的元素数量就是最终答案。

代码

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <sstream>
#include <numeric>

using namespace std;

void read_line_to_deque(deque<int>& q) {
    string line;
    getline(cin, line);
    stringstream ss(line);
    int num;
    while (ss >> num) {
        q.push_back(num);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    deque<int> supply_q, demand_q;
    read_line_to_deque(supply_q);
    read_line_to_deque(demand_q);

    while (!supply_q.empty() && !demand_q.empty()) {
        int current_supply = supply_q.front();
        supply_q.pop_front();

        int attempts = 0;
        int max_attempts = demand_q.size();

        while (!demand_q.empty() && attempts < max_attempts) {
            int first_demand = demand_q.front();

            if (current_supply < first_demand) {
                demand_q.push_back(demand_q.front());
                demand_q.pop_front();
                attempts++;
                continue;
            }

            if (current_supply == first_demand) {
                demand_q.pop_front();
            } else { // current_supply > first_demand
                long long current_sum = 0;
                int ships_to_supply = 0;
                for (int demand : demand_q) {
                    if (current_sum + demand <= current_supply) {
                        current_sum += demand;
                        ships_to_supply++;
                    } else {
                        break;
                    }
                }
                for (int i = 0; i < ships_to_supply; ++i) {
                    demand_q.pop_front();
                }
            }
            break; 
        }
    }

    cout << demand_q.size() << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String supply_line = sc.nextLine();
        String demand_line = sc.nextLine();

        Deque<Integer> supply_q = new LinkedList<>();
        Deque<Integer> demand_q = new LinkedList<>();

        for (String s : supply_line.split(" ")) {
            supply_q.add(Integer.parseInt(s));
        }
        for (String s : demand_line.split(" ")) {
            demand_q.add(Integer.parseInt(s));
        }

        while (!supply_q.isEmpty() && !demand_q.isEmpty()) {
            int current_supply = supply_q.poll();
            
            int attempts = 0;
            int max_attempts = demand_q.size();

            while (!demand_q.isEmpty() && attempts < max_attempts) {
                int first_demand = demand_q.peek();

                if (current_supply < first_demand) {
                    demand_q.add(demand_q.poll());
                    attempts++;
                    continue;
                }

                if (current_supply == first_demand) {
                    demand_q.poll();
                } else { // current_supply > first_demand
                    long current_sum = 0;
                    int ships_to_supply = 0;
                    for (int demand : demand_q) {
                        if (current_sum + demand <= current_supply) {
                            current_sum += demand;
                            ships_to_supply++;
                        } else {
                            break;
                        }
                    }
                    for (int i = 0; i < ships_to_supply; i++) {
                        demand_q.poll();
                    }
                }
                break;
            }
        }
        System.out.println(demand_q.size());
    }
}

import collections

# 读取输入
try:
    s_list = list(map(int, input().split()))
    d_list = list(map(int, input().split()))
except (ValueError, IndexError):
    # 根据题意，输入为空或格式不合法时应处理，但示例未明确输出-1，此处按常规处理
    s_list, d_list = [], []

supply_q = collections.deque(s_list)
demand_q = collections.deque(d_list)

while supply_q and demand_q:
    current_supply = supply_q.popleft()
    
    attempts = 0
    max_attempts = len(demand_q)
    
    while demand_q and attempts < max_attempts:
        first_demand = demand_q[0]
        
        # 规则 3: 需求不足
        if current_supply < first_demand:
            demand_q.rotate(-1) # 将队首元素移到队尾
            attempts += 1
            continue
            
        # 规则 1: 精准匹配
        if current_supply == first_demand:
            demand_q.popleft()
        
        # 规则 2: 超量分配
        else: # current_supply > first_demand
            current_sum = 0
            ships_to_supply = 0
            for demand in demand_q:
                if current_sum + demand <= current_supply:
                    current_sum += demand
                    ships_to_supply += 1
                else:
                    break
            
            for _ in range(ships_to_supply):
                demand_q.popleft()
        
        # 规则1或2执行完毕，当前补给舰消耗完毕
        break

print(len(demand_q))

算法及复杂度

  • 算法：队列模拟
  • 时间复杂度：，其中 是补给舰数量， 是作战舰数量。在最坏情况下，对于每一艘补给舰，我们可能需要遍历整个作战队列来计算前缀和（规则2），或者将作战队列完整地旋转一圈（规则3）。
  • 空间复杂度：，用于存储两个队列。