Article From:https://www.cnblogs.com/sun915/p/9512613.html

D14559. production scheduling”

Time limit:1.0s Memory restriction:256.0MB
Input file name:test.in Output file name:test.out
Problem description
  A factory received orders for n products, which were processed in two workshops A and B, and must be processed in workshop A before being processed in workshop B.
  The processing time of a product I in A and B two workshop is Ai and Bi respectively. How to arrange the processing sequence of the N products in order to make the total processing time shortest? The processing time here refers to the time from the beginning of processing the first product to the end of all the products have been processed in the A and B workshops.
Input format
  The first row is only a data n (0< n< 1000), representing the number of products.
  The next N data is the time required for each n product to be processed in the A workshop.
  The last N data is the time required for each n product to be processed in the B workshop (all integers).
Output format
  Only one line or one data indicates the least processing time.
sample input
5
3 5 8 7 10
6 2 1 4 9
sample output
34

Code:

#include<bits/stdc++.h>
#define tim first
#define id second

using namespace std;

int ans[1010], ta[1010], tb[1010];
pair<int, int> m[1010];
int n;

void readp() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> ta[i];
    for (int i = 1; i <= n; i++)
        cin >> tb[i];
}

void work() {
    for (int i = 1; i <= n; i++) {
        m[i].tim = min(ta[i], tb[i]);
        m[i].id = i;
    }
    sort(m + 1, m + n + 1);
    int l = 0, r = n + 1;
    for (int i = 1; i <= n; i++) {
        if (m[i].tim == ta[m[i].id]) {
            l ++;
            ans[l] = m[i].id;
        }
        else {
            r --;
            ans[r] = m[i].id;
        }
    }
    int tia = 0, tib = 0;
    for (int i = 1; i <= n; i++) {
        tia += ta[ans[i]];
        if (tia > tib)
            tib = tia;
        tib += tb[ans[i]];
    }
    cout << tib << endl;
}

int main(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    readp();
    work();
    return 0;
}

Similar Posts:

    None Found

Link of this Article: Production scheduling

Leave a Reply

Your email address will not be published. Required fields are marked *