可(kŏng)爱(bÙ)的测试

# 排序(sort)

## 问题描述
达人们的聚会还在继续，来自嵊州的一位女生对排序类问题有特别的研究，她给大家出了一个题目。

给定n个整数 $a_i$ 和一个整数 $m$ ，对于所有$1 \leq i \leq n$和$1\leq j\leq n$，求出$a_i+a_j$，然后将所有求得的$n^2$个$a_i+a_j$的数值从大到小排序，你需要求出排序后前$m$个数的和。

## 输入格式

第一行两个整数$n$和$m$，第二行$n$个整数表示$a_i$。

## 输出格式

一行一个整数，表示答案。

## 样例 #1

### 样例输入 #1

```
5 3
10 14 19 34 33
```

### 样例输出 #1

```
202
```

## 样例 #2

### 样例输入 #2

```
9 14
1 3 5 110 24 21 34 5 3
```

### 样例输出 #2

```
1837
```

## 数据范围
对于$20\%$的数据，$n\leq 50$；

对于$40\%$的数据，$ n\leq 500$；

对于另$10\%$的数据，保证$m\leq 500$；

对于另$20\%$的数据，保证$m\leq 100000$；

对于所有数据，$1\leq n$，$a[i]\leq 100000$，$0\leq m\leq n^2$。

## 理所应当地想到暴力
```
#include <bits/stdc++.h>
using namespace std;
//#define int long long
int a[100005];
vector<int> b;
signed main()
{
//	freopen("sort.in","r",stdin);
//	freopen("sort.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			b.push_back(a[i]+a[j]);
		}
	}
	sort(b.begin(),b.end(),greater<int>());
	long long ans = 0;
	for(int i=0;i<m;i++) ans += b[i];
	cout<<ans;
	return 0;
}
```
40!!!

## 突然想到了某STL容器
 `priority_queue`!
 
自动排序！

`priority_queue`的基本函数

1. `push(x)` ：将$x$入队，并排序，$O(logN)$

1. `top()`：获得队首元素，$O(1)$

1. `pop()`：队首出队，$O(logN)$

1. `empty()`：检测是否为空，$O(1)$

1. `size()`:返回队列大小（元素个数），$O(1)$

* `priority_queue` 默认从小到大排序
>
> ```
> priorty_queue<int> q;
> ```
> 从大到小
>
> ```
> priority_queue<int,vector<int>,greater<int> > q;
> ```
> 从小到大
> * `<` `>` 内可改为数据名称，如 `prioity_queue<NODE> q` 或 `prioity_queue<long long> q`
  
```
#include <bits/stdc++.h>
using namespace std;
//#define int long long
int a[100005];
priority_queue<int,vector<int>,greater<int> > q;
// 不知道为什么，反正记住 
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n,greater<int>());
	int s = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			q.push(a[i]+a[j]);
			s++;
			if(s>m)
			{
				q.pop();
				if(a[i]+a[j]<q.top()) break;
				//如果a[i]+a[j]<q.top(),那么a[i+1]+a[j+1]一定小于q.top(),想想为什么
			}
		}
	}
	long long ans = 0;
	while(!q.empty())
	{
		ans += q.top();
		q.pop();
	}
	cout<<ans;
	return 0;
}
```
按下`Ctrl+A`

$\text{\color{FFFFFF}\Huge{我聪明吧}}$
  
## 当然，还有其他方法
  
某 deng 告诉我的，只管抄，保证 $\color{52C41A}AC$
  
```
#include <bits/stdc++.h>
using namespace std;
//#define int long long
int a[100005];
long long s[100005];//前缀和 
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	long long m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++) s[i] = s[i-1]+a[i];
	long long ans;
	long long cnt;
	long long res;
	int l = 0;
	int r = 200005;
	//二分 
	while(l<=r)
	{
		int mid = (l+r)>>1;//可能的和 
		res=0;
		cnt=0;
		int pos=n+1;
		for(int i=1;i<=n;i++)
		{
			while(pos>1&&a[pos-1]>=mid-a[i]) pos--;
			//找到满足a[pos]+a[i]>=mid的pos的最小值 
			cnt += n-pos+1;//不满足的数量
			res += 1ll*(n-pos+1)*a[i]+s[n]-s[pos-1];
			/**********************************\
			|1ll差不多就是              	   |
			| void 1ll()                	   |
			| {                         	   |
			| 	long long x = 1        		   |
			| 	return 1                	   |
			| }                         	   |
			|简单点说就是                      |
			|		一个数据类型为long long 的1| 
			\**********************************/
		}
		if(cnt>=m)
		{
			ans = mid; 
			l = mid+1;
		} 
		else r = mid-1;
	}
	cout<<res-(cnt-m)*ans;
	return 0;
}

```
再按下`Ctrl+A`

$\text{\color{FFFFFF}\Huge{还不错吧，点个赞再走}}$