题目链接:http://codeforces.com/contest/1165/problem/E
题意:
改变数组B的顺序,使得最小
我们可以把 a[i] * (i + 1)*(n - i) 可以处理成定值,然后从大到小排序与从小到大排序的b数组相乘即为答案
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <set> #include <vector> #include <string> #include <cmath> #include <queue> #define rep(i, s, e) for(int i = s; i < e; ++i) #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define P pair<int, int> #define INF 0x3f3f3f3f #define Mod 998244353 using namespace std; typedef long long ll; static const int N = 305; static const int MAX_N = 2e5 + 5; ll a[MAX_N], b[MAX_N]; void solve(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); //ios::sync_with_stdio(false); int n; while(scanf("%d", &n) != EOF){ for(int i = 0; i < n; ++i){ ll v; scanf("%I64d", &v); a[i] = v * (i + 1) * (n - i); //这里不能先取模,不然后面排序的贪心策略就会有问题 } for(int i = 0; i < n; ++i) scanf("%I64d", &b[i]); sort(a, a + n, greater<ll>()); sort(b, b + n); ll ans = 0; for(int i = 0; i < n; ++i) ans = (ans + (a[i] % Mod) * b[i]) % Mod; printf("%I64d\n", ans); } } int main() { solve(); return 0; }View Code