接网站开发哪里好,wordpress4.9安装出错,常德论坛市民留言尚一网,怎么在网站做视频接口正题
luogu 6877 题目大意
给你n1个数aia_iai和n个数bib_ibi#xff0c;cic_ici为不选aia_iai时#xff0c;重新调整剩下n个数的位置后#xff0c;∑i1nmax(ai−aj)\sum \limits_{i1}^{n}max(a_i-a_j)i1∑nmax(ai−aj)的最小值,求c数组 解题思路
不难发现让…正题
luogu 6877 题目大意
给你n1个数aia_iai和n个数bib_ibicic_ici为不选aia_iai时重新调整剩下n个数的位置后∑i1nmax(ai−aj)\sum \limits_{i1}^{n}max(a_i-a_j)i1∑nmax(ai−aj)的最小值,求c数组 解题思路
不难发现让a,b大的对大的小的对小的可以得到最小值
那么可以先对a,b排序让前n个数先匹配然后把ana_nan换成an1a_{n1}an1因为an1ana_{n1}a_nan1an所以答案只会变大
按这个方法倒着进行一遍就可以求出答案了 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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换成i1sort(a 1, a 1 n 1, cmpp);//排回去for (int i 1; i n 1; i)printf(%d , a[i].ans);return 0;
}
