题解 | #加工生产调度#

思路

不得不说这个排序方法真的很妙。
设定每个零件有x,y,id,分别表示在A车间加工时间，在B车间加工时间，以及编号。
我们比较两个零件的优先级时，加入A应该在B之前加工，那么A.x+B.y+max(A.y,B.x)<B.x+A.y+max(A.x,B.y)
已知min(x,y)+max(x,y)=x+y，那么上式就可以化为min(A.x,B.y)<min(A.y,B.x);
我们以这个规则对所有零件进行排序（如果存在相等的情况，那么优先加工A区间加工时间少的），
问题就解决啦！

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn=2005;

int n;
struct E{
    int x,y,id; //记录每个零件 
}s[maxn];

bool cmp(E a,E b){
    int i= min(a.x,b.y),j=min(a.y,b.x);
    if(i==j) return a.x<b.x; //没有这一步只能过洛谷不能过牛客 
    return i<j;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) s[i].id=i;
    for(int i=1;i<=n;i++) cin>>s[i].x;
    for(int i=1;i<=n;i++) cin>>s[i].y;
    sort(s+1,s+1+n,cmp); //排序 
    int tmp=0,sum=0;//tmp为B车间的工作时间 
    for(int i=1;i<=n;i++){
        tmp-=s[i].x;
        if(tmp<0) tmp=0;
        tmp+=s[i].y;
        sum+=s[i].x; 
    } 
    sum+=tmp; //A车间工作完后B车间还需工作tmp 
    cout<<sum<<"\n";
    for(int i=1;i<=n;i++){
        cout<<s[i].id<<" ";
    }
    return 0;
}