当前位置：首页 > news >正文

lqb日志08

news 2025/6/28 12:06:38

一只小蒟蒻备考蓝桥杯的日志

文章目录

- 笔记
- - 坐标相遇判断
  - 工作调度问题（抽象时间轴绘制）
- 刷题
- 心得
- 小结

笔记

坐标相遇判断

在这里插入图片描述
我是小懒虫，碰了一下运气，开了个“恰当”的数（7000）如果，7000次还不能抓到牛，就算不能

工作调度问题（抽象时间轴绘制）

在这里插入图片描述

方案一源码网址
在这里插入图片描述

在这里插入图片描述
方案二（我写完才发现…实现的是它…)

#include <stdio.h>
#include <iostream>
#include <string.h>using namespace std;int main() {int m, n; //m:机器数（工序数） n:工件数cin >> m >> n;int squeue[m * n + 5];
//	getchar();for(int i = 1; i <= m * n; i++) {cin >> squeue[i];}int single[n + 5][m + 5];for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {cin >> single[i][j];}
//		cin >> single[i][0] >> single[i][1];// single[i][j] 第i个工件的第j个工序需要的机器}int time[n + 5][m + 5];for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {cin >> time[i][j];}
//		cin >> time[i][0] >> time[i][1];// time[i][j] 第i个工件的第j个工序花费的时间}int finished[n + 5][3]; // finished[i]  第i个工件 // 0:第x个工序已经完成了 1:时间已经耗费yfor(int i = 1; i <= n; i++) {finished[i][0] = 0;finished[i][1] = 0;}
//	memset(finished, 0, sizeof(finished)); int machine_used[m + 5]; // 机器i的占用时间已经排到machine[i]了memset(machine_used, 0, sizeof(machine_used));for(int r = 1; r <= m * n; r++) {int checked_machine_num = 0;bool checked_machine[m + 5];memset(checked_machine, false, sizeof(checked_machine));for(int t = r; t <= m * n && checked_machine_num <= m; t++) {int gongjian = squeue[t];// 这次轮到squeue[t]工件来用机器啦// 需要的机器是 single[gongjian][(finished[gongjian][0]+1)]// 第 finished[gongjian][0] 个工序已完成// 对应时间已经排到 [1]int machine_inneed = single[gongjian][(finished[gongjian][0] + 1)];if(checked_machine[machine_inneed] == false) {checked_machine[machine_inneed] = true;checked_machine_num++;int the_earliest_usetime = (machine_used[machine_inneed] > finished[gongjian][1] ? machine_used[machine_inneed] : finished[gongjian][1]);machine_used[machine_inneed] = the_earliest_usetime + time[gongjian][finished[gongjian][0] + 1];finished[gongjian][1] = the_earliest_usetime + time[gongjian][finished[gongjian][0] + 1];finished[gongjian][0]++;cout << gongjian << ":" << endl;cout << "已完成工序数:" << finished[gongjian][0] << "  " << "时间已达:" << finished[gongjian][1] << endl;}} }return 0;
}

刷题

P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two
P1065 [NOIP2006 提高组] 作业调度方案没有真的写出来，看我心情再手写吧，好麻烦，有点性价比不太高

心得

第1题（抓牛）避大雷！

我嘞个逗，getline 决定了 mp[i][j] i 是行号，就是正常 x-y 坐标轴的 y ！
所以，后面的（数组下标模拟坐标移动）都写错了…
我嘞个逗，又写错了，这个 x 方向是向下的

以后一行行读入，注意它xy轴真正含义，以及递增方向
第2题，小蒟蒻要yue出来啦！好bt的模拟题…
(崩溃…小蒟蒻难得写这么多注释…)

崩溃+1，写完发现，自己的算法实现的是弃用的方案二…
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/95c4c73f1aec4185ab9cbd400bf35fa6.png = 800x)
模拟，用时间轴插空+屡次遍历
不过，感觉这题，想要真正理解题意，还蛮困难的…