4 solutions

  • 1
    @ 2024-9-1 18:29:35

    塔子哥牛逼

    • 0
      @ 2024-9-23 20:01:18

      答案c++的是不是多写了点？

      #include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm> // 包含lower_bound
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n,vector<int>(2));

    for (int i = 0; i <n; i++)
    {
        cin >> a[i][0]>> a[i][1];
    }
    sort(a.begin(),a.end(),[](const vector<int>&x,const vector<int>&y){
        return x[0]<y[0];
    });
    int start=0;
    priority_queue<int,vector<int>,greater<int>> queue;
    int idx=0;
    int ans=0;
    while (idx<n||!queue.empty()) {
        //移除结束的
        while (!queue.empty()&&queue.top()<start) {
            queue.pop();
        }
      
        //没有可以参观的,更新开始时间
        if (queue.empty()) {
            if (idx==n) {
             break;
            }
          start=max(start,a[idx][0]);
        }
        //添加参观的博览会
        while (idx<n&&a[idx][0]<=start) {
          queue.push(a[idx][1]);
          idx++;
        }

        for (int i=0; i<k; i++) {
            if (!queue.empty()) {
              ans++;
              queue.pop();
            }
        
        }
        start++;
    }
    cout<<ans<<endl;
}
      • 0
        @ 2024-9-22 17:01:49 
        import heapq
n,k = list(map(int, input().strip().split(' ')))

meets = []

for i in range(n):
    s,e = list(map(int, input().strip().split(' ')))
    meets.append([s,e])

meets.sort(key=lambda x:x[0])

idx = 0
queue = []#记录可以参加的会的结束时间
start = meets[0][0]
ans=0
while idx<n or queue:
    while idx<n and meets[idx][0]<=start:
        if meets[idx][1]>=start:#已经开始且尚未结束的会，记录
            heapq.heappush(queue,meets[idx][1])
        idx+=1

    for i in range(k):#参会
        if queue:
            heapq.heappop(queue)
            ans+=1
    
    
    if queue:#还有可参加的会，增加一天，第二天再去
        start+=1 #更新一天
    elif idx<n:#没有可参加的，找到最近可参会的一天
        start = meets[idx][0]

    while queue and queue[0]<start:#新的一天，移除已经结束的会
        heapq.heappop(queue)

print(ans)
        • 0
          @ 2024-8-28 20:12:18

          题面描述:

          有nn场博览会将举办，第ii场博览会的举办时间为从第startistart_i天到第endiend_i天（包含这两天）。小塔每天最多可以参加kk场博览会，且不需要全程参加某场博览会，只需在某一天参加即可。给定博览会的数量nn和每天最多可参加的博览会数量kk，以及每场博览会的举办时间[starti,endi][start_i, end_i]，请问小塔最多可以参加多少场博览会。输入包括两整数nn和kk，接下来nn行是博览会的时间范围[starti,endi][start_i, end_i]。输出为小塔最多能参加的博览会数量。

          题意化简

          给定k个时间区间[x,y],从左到右每天只能选择k个时间区间。问最多能选多少个区间？

          思路：贪心 + 优先队列

          LeetCode 1353. 最多可以参加的会议数目的变种。

          大家如果会做上面这个题，就会做本题。思想很简单。

          贪心性质:对于第 i 天，如果有若干的会议都可以在这一天开，那么我们肯定是让 endDay 小的会议先在这一天开才会使答案最优，因为 endDay 大的会议可选择的空间是比 endDay 小的多的，所以在满足条件的会议需要让 endDay 小的先开。

          做法:考虑随时间推移，维护一个按结束时间排序的小根堆，然后在每个时间戳，从堆里连续取k个出来解决掉即可。

          解题思路

          要解决这个问题，可以从以下两点进行考虑：

          1. 贪心策略的选择：

            • 在某一天，如果有多个博览会可以选择参加，优先选择结束时间（即endiend_i）较早的博览会。因为结束时间较晚的博览会有更多天可以选择，结束时间较早的博览会选择的空间较小，这样可以避免浪费可选的天数。因此，每次都应该优先参加结束时间较早的博览会。

          2. 利用最小堆：

            • 我们需要随时从当前可以参加的博览会中选择结束时间最早的几个。最小堆是一种合适的数据结构，因为它可以帮助我们在O(log⁡n)O(\log n)的时间复杂度内找到最早结束的博览会。
            • 我们从起始的时间戳开始，按时间推移，每天从当前可参加的博览会中取出kk场，并将它们从堆中移除，直到所有博览会都被处理完为止。

          具体步骤

          1. 输入数据：我们读取nn个博览会的起止时间[starti,endi][start_i, end_i]。

          2. 排序：首先按照博览会的开始时间startistart_i进行排序。这样可以保证我们在时间流逝的过程中，按顺序处理所有博览会。

          3. 最小堆的使用：我们使用一个最小堆queue来存储当前可以参加的博览会的结束时间，堆的性质保证了我们总能先处理掉结束时间最早的博览会。

          4. 贪心策略执行：

            • 对于每一个时间戳，我们首先移除掉那些已经结束的博览会（即结束时间小于当前时间的博览会）。
            • 然后将当前可以参加的博览会加入到堆中（这些博览会的开始时间小于等于当前时间）。
            • 接着从堆中取出最多kk个结束时间最早的博览会，记录参加的数量。

          5. 时间推进：如果某个时间戳没有博览会可参加，则将时间推进到下一个可以参加博览会的开始时间。

          代码

          python

          import heapq

n, k = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]

# 根据开始时间排序
a.sort(key=lambda x: x[0])

# 模拟当前的时间
start = 0
# 优先队列，存储结束时间
queue = []
# 当前博览会的索引, 从0开始，从小往大遍历
idx = 0
# 参加的博览会数量
ans = 0

while idx < n or queue:
    # 移除已结束的博览会
    while queue and queue[0] < start:
        heapq.heappop(queue)

    # 添加当前可以参加的博览会
    while idx < n and a[idx][0] <= start:
        heapq.heappush(queue, a[idx][1])
        idx += 1

    # 如果没有可参加的博览会，更新开始时间
    if not queue:
        if idx == n:
            break
        start = max(start, a[idx][0])
    while idx < n and a[idx][0] <= start:
        heapq.heappush(queue, a[idx][1])
        idx += 1
    # 参加博览会
    for _ in range(k):
        if queue:
            ans += 1
            heapq.heappop(queue)

    start += 1

print(ans)

          Java

          import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] input = new int[n][2];
        for (int i = 0; i < n; i++) {
            input[i][0] = sc.nextInt();
            input[i][1] = sc.nextInt();
        }
        sc.close();
        // 按开始时间排序
        Arrays.sort(input, (a, b) -> Integer.compare(a[0], b[0]));
        // 小根堆（按结束时间排序）
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        int i = 0, d = input[0][0], res = 0;
        while (i < n || !pq.isEmpty()) {
            // 添加所有开始时间小于等于当前时间 d 的事件到优先队列
            while (i < n && input[i][0] <= d) {
                pq.add(input[i++]);
            }
            // 移除所有结束时间小于当前时间 d 的事件
            while (!pq.isEmpty() && pq.peek()[1] < d) {
                pq.poll();
            }
            // 处理当前时间 d 上的最多 k 个事件
            int j = 0;
            while (!pq.isEmpty() && j < k) {
                pq.poll();
                res++;
                j++;
            }
            d++;
        }

        System.out.println(res);
    }
}

          Cpp

          #include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int n, k; // 输入博览会的数量n和每次可以参加的博览会数量k
    cin >> n >> k;
    
    vector<vector<int>> a(n, vector<int>(2)); // 用于存储博览会的开始和结束时间
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1]; // 读取开始和结束时间
    }

    // 根据开始时间排序
    sort(a.begin(), a.end(), [](const vector<int>& x, const vector<int>& y) {
        return x[0] < y[0];
    });

    int start = 0; // 当前时间
    priority_queue<int, vector<int>, greater<int>> queue; // 最小堆用于存储结束时间
    int idx = 0; // 当前处理的博览会索引
    int ans = 0; // 参加的博览会数量

    while (idx < n || !queue.empty()) {
        // 移除已结束的博览会
        while (!queue.empty() && queue.top() < start) {
            queue.pop();
        }

        // 添加当前可以参加的博览会
        while (idx < n && a[idx][0] <= start) {
            queue.push(a[idx][1]); // 将结束时间加入优先队列
            idx++;
        }

        // 如果没有可参加的博览会，更新开始时间
        if (queue.empty()) {
            if (idx == n) {
                break;
            }
            start = max(start, a[idx][0]);
        }
        while (idx < n && a[idx][0] <= start){
            queue.push(a[idx][1]);
            idx++;
        }
        // 参加博览会
        for (int i = 0; i < k; i++) {
            if (!queue.empty()) {
                ans++; // 参加博览会
                queue.pop(); // 弹出结束时间
            }
        }

        start++; // 增加当前时间
    }

    cout << ans << endl; // 输出参加的博览会数量
    return 0; // 结束程序
}

          OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

          • 1

          2024.8.28-秋招-第3题-参加博览会

          Information

          ID
          106
          Time
          1000ms
          Memory
          256MiB
          Difficulty
          8
          Tags
          # Submissions
          854
          Accepted
          108
          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, 46ms
          4. Powered by Hydro v4.14.1 Community