P1248 加工生产调度 贪心

2024-01-10 11:31:20

加工生产调度

传送门

题目描述

某工厂收到了 n n n 个产品的订单,这 n n n 个产品分别在 A、B 两个车间加工,并且必须先在 A 车间加工后才可以到 B 车间加工。

某个产品 i i i 在 A、B 两车间加工的时间分别为 A i , B i A_i,B_i Ai?,Bi?。怎样安排这 n n n 个产品的加工顺序,才能使总的加工时间最短。

这里所说的加工时间是指:从开始加工第一个产品到最后所有的产品都已在 A、B 两车间加工完毕的时间。

输入格式

第一行仅—个整数 n n n,表示产品的数量。

接下来一行 n n n 个整数是表示这 n n n 个产品在 A 车间加工各自所要的时间。

最后的 n n n 个整数是表示这 n n n 个产品在 B 车间加工各自所要的时间。

输出格式

第一行一个整数,表示最少的加工时间。

第二行是一种最小加工时间的加工顺序。

样例 #1

样例输入 #1

5
3 5 8 7 10
6 2 1 4 9

样例输出 #1

34
1 5 4 2 3

提示

1 ≤ n ≤ 1000 1\leq n\leq 1000 1n1000

以上来自洛谷 以上来自洛谷 以上来自洛谷

解题思路

前言

是紫题,做不出来没逝

正文

首先明确,每个产品都要被加工。则A车间的总时间是可以确定的就是 s u m ( a i ) sum(a_i) sum(ai?),影响结束时间的,是最终B车间何时结束。可以想到,使得B车间加工时间大于 s u m ( b i ) sum(b_i) sum(bi?)的有两个因素:第一个产品A车间加工结束后,B车间才开始加工,B车间一开始有一段等待时间;B车间产品加工完毕,下一个产品还在A车间加工,B车间产品加工之间是可能存在等待时间的。
所以总体思路应该是使B车间第一个产品加工时间尽可能提前,且产品之间的等待时间尽可能减少。所以可以想到,应该让A车间加工时间最短的产品先加工,B车间加工时间最短的产品要尽可能放在最后加工,时间长的放在前面加工。
c i = m i n ( a i , b i ) c_i=min(a_i,b_i) ci?=min(ai?,bi?),对产品 c i c_i ci?从小到大排序。对于 a i < b i a_i<b_i ai?<bi?,可见放在开始,B车间加工时间赶不上A车间加工时间,就不会出现B车间等待的情况;对于 a i > b i a_i>b_i ai?>bi?,可见放在结尾,A车间加工时间赶不上B车间加工时间,就能使B车间等待队列更早地结束。(正文中变量名与实际代码不符,仅做参考用。)

AC Code

// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <Licenses - GNU Project - Free Software Foundation>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
	#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
	#include <ccomplex>
	#include <cfenv>
	#include <cinttypes>
	#include <cstdalign>
	#include <cstdbool>
	#include <cstdint>
	#include <ctgmath>
	#include <cwchar>
	#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
	#include <array>
	#include <atomic>
	#include <chrono>
	#include <condition_variable>
	#include <forward_list>
	#include <future>
	#include <initializer_list>
	#include <mutex>
	#include <random>
	#include <ratio>
	#include <regex>
	#include <scoped_allocator>
	#include <system_error>
	#include <thread>
	#include <tuple>
	#include <typeindex>
	#include <type_traits>
	#include <unordered_map>
	#include <unordered_set>
#endif
using namespace std;
#define int long long
const int Maxn = 1000 + 5;
int n, a[Maxn], b[Maxn];
int minn[Maxn], tmp[Maxn], k, tot;
int ans[Maxn];
inline void work() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}
	for (int i = 1; i <= n; i++) {
		minn[i] = min(a[i], b[i]);
		tmp[i] = i;
	}
	for (int i = 1; i <= n - 1; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (minn[i] > minn[j]) {
				swap(minn[i], minn[j]);
				swap(tmp[i], tmp[j]);
			}
		}
	}
	k = 0;
	tot = n + 1;
	for (int i = 1; i <= n; i++) {
		if (minn[i] == a[tmp[i]]) {
			k++;
			ans[k] = tmp[i];
		} else {
			tot--;
			ans[tot] = tmp[i];
		}
	}
	k = 0;
	tot = 0;
	for (int i = 1; i <= n; i++) {
		k += a[ans[i]];
		if (tot < k) {
			tot = k;
		}
		tot += b[ans[i]];
	}
	cout << tot << endl;
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}

文章来源:https://blog.csdn.net/BestMonkey/article/details/135482223
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。