「Nhk R1 D」Apocryphal Vir Pulcher

假如我知道这个值的第k小,那么它选择第k+1小是不是有n种选择.

所以就类似bfs,但是在bfs过程中会产生重复,什么重复呢,就是我现在是1搜3,搜出来是1+3,我现在是3搜1,搜出来是3+1,但是两者在题目中属于同一种含义.

所以我们简单的去重一下,就像定义两个for都从1开始循环,我们只要把两个for第一个for定义从1开始循环,第二个for定义从i开始循环,就不重不漏的记录了,同时用n个单调队列就可以$O(N\ast K)\{O(N*K)\}$解决了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=85;
queue<int>q[N];
int a[N];
//类bfs解决.

int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int num=0;ll mi;
	for(int i=1;i<=k;i++)
	{
		mi=1e18;
		if(i==1)	mi=0;
		for(int j=1;j<=n;j++)
		{
			if((int)q[j].size()&&mi>q[j].front())
			{
				num=j;
				mi=q[j].front();
			}
		}
		if((int)q[num].size())q[num].pop();
		for(int j=num;j<=n;j++)
			q[j].push(a[j]+mi);
	}
	printf("%lld\n",mi);
	return 0;
}