? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 加工生產調度
題目描述
某工廠收到了n個產品的訂單，這n個產品分別在A、B兩個車間加工，并且必須先在A車間加工后才可以到B車間加工。

某個產品i在A、B兩車間加工的時間分別為Ai、Bi。詢問怎樣安排這n個產品的加工順序，才能使總的加工時間最短。這里所說的加工時間是指：從開始加工第一個產品到最后所有的產品都已在A、B兩車間加工完畢的時間。

輸入格式：
第一行僅—個數據n(0<n<1000)，表示產品的數量。

接下來n個數據是表示這n個產品在A車間加工各自所要的時間（都是整數）。

最后的n個數據是表示這n個產品在B車間加工各自所要的時間（都是整數）。

輸出格式：
第一行一個數據，表示最少的加工時間。

第二行是n個整數，均為產品的原始標號，表示一種用時最短的產品加工順序。

輸入樣例：
5
3 5 8 7 10
6 2 1 4 9
輸出樣例：
34
1 5 4 2 3
?

解析：

???????這是一道很經典的題，只需要記住這種題型的一個結論：

???????A機器上加工時間短的任務應優先，而在B機器上加工時間短的任務應該排在后面。

?????

???????以下為證明過程：

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; const int M=1e6+10; int n,m,sum,sum1=0,ans=0; int w[M],a[M],b[M]; struct node {int x,id; } dp[M]; bool cmp(node u,node v) {return u.x<v.x; } int main() {scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&a[i]);for(int i=1; i<=n; i++)scanf("%d",&b[i]);for(int i=1; i<=n; i++)dp[i].id=i,dp[i].x=min(a[i],b[i]);sort(dp+1,dp+n+1,cmp);int x=1,y=n;for(int i=1; i<=n; i++){if(dp[i].x==a[dp[i].id])w[x++]=dp[i].id;elsew[y--]=dp[i].id;}for(int i=1; i<=n; i++){sum1+=a[w[i]];if(sum1>ans)ans=sum1;ans+=b[w[i]];}printf("%d\n",ans);for(int i=1; i<n; i++)printf("%d ",w[i]);printf("%d\n",w[n]);return 0; }

?

總結

以上是生活随笔為你收集整理的#10003. 「一本通 1.1 例 4」加工生产调度（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。