CodeForces 1165E Two arrays and the sum of functions (思维)

题目链接:http://codeforces.com/contest/1165/problem/E

题意:
CodeForces 1165E Two arrays and the sum of functions (思维)

改变数组B的顺序,使得CodeForces 1165E Two arrays and the sum of functions (思维)最小

CodeForces 1165E Two arrays and the sum of functions (思维)

我们可以把 a[i] * (i + 1)*(n - i) 可以处理成定值,然后从大到小排序与从小到大排序的b数组相乘即为答案

CodeForces 1165E Two arrays and the sum of functions (思维)
#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

 

上一篇:Microsoft Azure Function Apps 功能应用程序简介


下一篇:Building Unicode applications in MFC(转载)