商业分割
[YRQ YRQ YRQ YRQ YRQ
]
上回书说到 我们已经有了这个式子
[min(b_j,a_i) leq min(b_i,a_j)
]
那么我们是怎么由这个式子推导到
的呢？
推导排序关键字
同样，我们可以设 (N_1)为 a < b 的作业集合，设(N_2)为 a > b 的作业集合，将 (N_1) 的作业集合按照(a_i)升序排列，将(N_2) 的按照(b_i)降序排列。(N_1)放在(N_2)后面构成最优顺序。
对于i < j,应当满足的条件是
[min(b_j,a_i) leq min(b_i,a_j)
]
那么如果i,j都在(N_1)集合里面，那么(min(b_j,a_i) = a_i,min(b_i,a_j) = a_j)，也就是按照a的升序排列
如果i，j都在集合(N_2)里面，那么(min(b_j,a_i) = b_j,min(b_i,a_j) = b_i)，也就是按照b的降序排列
如果i在(N_1)中，j在(N_2)中，那么就有
[a_i < b_i \
a_j > b_j \
b_j < a_j
]
那么显然成立。
所以排序方式就已经确定了。
再搞一遍代码
#include<bits/stdc++.h>
using namespace std;
int ans[1005],n,k,i,j,t,a[1005];
int b[1005],m[1005],s[1005];
void read(){
cin >> n;
for(i = 1;i <= n;i++) cin >> a[i];
for(i = 1;i <= n;i++) cin >> b[i];
for(i = 1;i <= n;i++){ m[i]=min(a[i],b[i]);s[i]=i;}
}
void solve(){
for(i = 1;i <= n-1;i++)
for(j = i+1;j <= n;j++){
if(m[i] > m[j]) {swap(m[i],m[j]);swap(s[i],s[j]);}
}
k = 0;t = n + 1;
for(i = 1;i <= n;i++){
if(m[i] == a[s[i]]){k++;ans[k] = s[i];}
else {t--;ans[t] = s[i];}
}
k = 0;t = 0;
for(i = 1;i <= n;i++){
k += a[ans[i]];
if(t < k) t = k;
t += b[ans[i]];
}
cout << t << endl;
for(i = 1;i <= n;i++) cout << ans[i] << ' ';
cout << endl;
}
int main(){
read();
solve();
return 0;
}//lcez_cyc