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:时间已经耗费y
	for(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，写完发现，自己的算法实现的是弃用的方案二…

模拟，用时间轴插空+屡次遍历
不过，感觉这题，想要真正理解题意，还蛮困难的…