正題

luogu 6877

---

題目大意

給你n+1個數$a_i$和n個數$b_i$，$c_i$為不選$a_i$時，重新調整剩下n個數的位置后，$\sum _{i=1}^{n}max(a_i?a_j)$的最小值,求c數組

---

解題思路

不難發現讓a,b大的對大的，小的對小的可以得到最小值

那么可以先對a,b排序，讓前n個數先匹配，然后把$a_n$換成$a_{n+1}$，因為$a_{n+1}>a_n$，所以答案只會變大

按這個方法倒著進行一遍就可以求出答案了

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 200021 using namespace std; int n, b[N], ans[N]; struct node {int v, s, ans; }a[N]; bool cmp(node a, node b) {return a.s < b.s; } bool cmpp(node a, node b) {return a.v < b.v; } int main() {scanf("%d", &n);for (int i = 1; i <= n + 1; ++i){scanf("%d", &a[i].s);a[i].v = i;}for (int i = 1; i <= n; ++i)scanf("%d", &b[i]);sort(a + 1, a + 1 + n + 1, cmp);//排序sort(b + 1, b + 1 + n);for (int i = 1; i <= n; ++i)a[n + 1].ans = max(a[n + 1].ans, a[i].s - b[i]);//前n個匹配for (int i = n; i > 0; --i)a[i].ans = max(a[i + 1].ans, a[i + 1].s - b[i]);//把i換成i+1sort(a + 1, a + 1 + n + 1, cmpp);//排回去for (int i = 1; i <= n + 1; ++i)printf("%d ", a[i].ans);return 0; }

總結

以上是生活随笔為你收集整理的【结论】只不过是长的领带（luogu 6877）的全部內容，希望文章能夠幫你解決所遇到的問題。

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