lqb日志08

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

笔记

坐标相遇判断

我是小懒虫，碰了一下运气，开了个“恰当”的数（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;
}

刷题

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

心得

1. 第1题（抓牛）避大雷！
   
   我嘞个逗，getline 决定了 mp[i][j] i 是行号，就是正常 x-y 坐标轴的 y ！
   所以，后面的（数组下标模拟坐标移动）都写错了…
   我嘞个逗，又写错了，这个 x 方向是向下的
   
   以后一行行读入，注意它xy轴真正含义，以及递增方向
2. 第2题，小蒟蒻要yue出来啦！好bt的模拟题…
   (崩溃…小蒟蒻难得写这么多注释…)
   
   崩溃+1，写完发现，自己的算法实现的是弃用的方案二…
   
   模拟，用时间轴插空+屡次遍历
   不过，感觉这题，想要真正理解题意，还蛮困难的…

小结

今天专攻模拟，过了一道[普及/提高-]，盘明白了一道[普及/提高-]，差强人意吧。
明天，还有三道[普及/提高-]，再折腾一天模拟类的题，要进入下一个主题了！

加油! ! !

小蒟蒻好荣幸发现自己的备赛日志受到你的关注，2024寒假无特殊情况坚持日更！