# 14219: 【原4219】游戏策略

### 题目描述

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

## 输出

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

5 5
1 1 1 1 1
1
2
1
2
1

1
2
1
2
1

## 数据规模

$$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;
}