14219: 【原4219】游戏策略

题目描述

author: kstarxin 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4219

题目描述

助教喜欢玩一个MORPG（多人在线角色扮演）游戏，游戏的规则很简单：系统在每轮游戏中随机放出 \( n \) 只怪物，作为玩家如果能够杀死怪物，就能获得对应的经验奖励。但是助教的操作是在是太菜了，只会被怪物和dalao吊打。
于是助教在完成大作业之余苦练黑客技术，终于黑进了服务器给自己加了特权：助教可以在每一轮游戏正常玩家开始角逐之前先随意选择一些怪物，轻易将其杀死并获得对应的奖励。但是由于助教不想被封号，所以只能选择所有随机放出的怪物中的 \( k \) 只。为了权衡，现在助教希望知道对于不同的 \(k\) ,在游戏中他最多可以获得的经验奖励 \( E \) 是多少。

输入

第一行 \(T,n\) , \(T\) 表示有 \(T\) 次询问。
第二行 \(n\) 个正整数，每个数 \(a_i\) 表示杀死第 \(i\) 只怪物的对应奖励。
接下来 \(T\) 行，每行一个 \(k\) 。

输出

\(T\) 行，每行一个正整数 \(E\)，由于结果可能很大，请将每次询问的结果对 \(10^{9} + 7\) 取模。

输入样例

输出样例

数据规模

\(0 \le T \le 10^{6},0 \le n \le 2 \times 10^5\)
\(i\) 为正整数，且 \(1 \le i \le n\)
\(k\) 为正整数，且 \(1 \le k \le n, 0 \le a_i \le 10^9 \)

ligongzzz's solution

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

const int mod = int(1e9 + 7);
vector<int> value;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T, n;
    cin >> T >> n;

    for (int i = 0; i < n; ++i) {
        int temp;
        cin >> temp;
        value.push_back(temp);
    }

    sort(value.begin(), value.end(), [](int a, int b) {return a > b; });

    for (int i = 1; i < n; ++i)
        value[i] = (value[i - 1] + value[i]) % int(1e9 + 7);

    for (; T > 0; --T) {
        int temp;
        cin >> temp;
        cout << value[temp - 1] << "\n";
    }

    return 0;
}

q4x3's solution

/**
 * 排序
 **/
#include <iostream>
#include <stdio.h>
#define modd 1000000007
using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
    T* A = a + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    T* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    T* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
    if(hi - lo < 2) return;
    int mi = (lo + hi) / 2;
    mergeSort(lo, mi, A); mergeSort(mi, hi, A);
    merge(lo, mi, hi, A);
}

int T, n, tmp, a[200233];
long long b[200233];

int main() {
    scanf("%d%d", &T, &n);
    for(register int i = 0;i < n;++ i) {
        scanf("%d", &a[i]);
    }
    mergeSort(0, n, a);
    for(register int i = 1;i <= n;++ i) {
        b[i] = (b[i - 1] + (long long)a[n - i]) % modd;
    }
    for(register int i = 0;i < T;++ i) {
        scanf("%d", &tmp);
        printf("%lld\n", b[tmp]);
    }
}

Zsi-r's solution

#include <iostream>

using namespace std;

int main()
{
    int T, n ,p,q,max=0;
    int tmp;
    cin >> T >> n;

    int *elem = new int[n];
    int *query = new int[T];

    for (int i = 0; i < n;i++)
    {
        cin >> elem[i];
    }

    for (int i = 0; i < T;i++)
    {
        cin >> query[i];
        if(query[i] >max){
            max = query[i];
        }
    }

    for (int N = n; N > 0 ; N--)
    {   
        for (p = n ; p > n-N ; p--)
        {
            q = p - 1;
            if (elem[q] < elem[p])
            {
                tmp = elem[p];
                elem[p] = elem[q];
                elem[q] = tmp;
            }
            if (N == (n+1)-max)
                break;
        }
        if (N == (n+1)-max) break;
    }

    for (int i = 0; i < T;i++)
    {
        int sum=0;
        for (int j = 0; j < query[i];j++)
            sum += elem[j];
        cout << sum <<endl;
    }

    cout << endl;
    cout << max << endl;
    for (int i = 0; i < n;i++)
    {
        cout << elem[i] <<endl;
    }
    return 0;
}