链接：https://ac.nowcoder.com/acm/contest/332/H
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小B来到了一个异世界，成为了肥猪之王。
在这个异世界，共有n种肥猪，编号分别为1，...，n。
小B希望集齐这n种肥猪。
召集肥猪有两种方式：
1. 花费a[i]的金币召唤一只编号为i的肥猪。
2. 花费x的金币使所有已召集的肥猪进化。
即编号为i的肥猪编号变成i+1，特殊的，编号为n的肥猪编号变成1。

请问小B最少要花多少金币才能集齐n种肥猪。    

输入描述:

第一行两个正整数n,x
接下来n行，第i行一个正整数a[i]

输出描述:

一个数表示答案

示例1

输入

复制

2 10
1
20

输出

复制

12

示例2

输入

复制

4 10
1
2
3
4

输出

复制

10

备注:

1≤n≤2000,1≤x,a[i]≤109

题意：题意一开始把我弄蒙了，后来看了题解才发现题目里的第二条是，全部的猪都进化，注意这一点就没问题了。

题解：两种写法，一种是用数组写，一种是用优先队列写，总之，都是求区间最小值，为什么求区间最小值呢？因为第二条是全部进化，这样的话，比如说进行两次进化，那么3号就由1号来的，这样的话就需要找到1——3区间的最小值，因为这个区间里的经过<=2次就可以，题目说的不清楚，应该是满足小于等于进化次数。。

注意：如果题目卡常数的话，就要数组写了，不过卡常数的题目不多~~~，这个题不卡常数~~上代码，两种方法

数组：

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int MAX = 2222;
ll a[MAX],b[MAX];
int main(){
	ll ans=0;
	ll n,x;
	cin >> n >> x;
	for (int i = 0; i < n;i++){
		cin >> a[i];
		ans+=a[i];//ans是没进化的时候，得到全部的类型花的总金币
		b[i]=a[i];
	}
	ll tmp=ans;
	for (int i = 0; i < n;i++){
		for (int j = 0; j < n;j++){
			if(b[(i+j+1)%n]>a[j]){//找区间最小值的方法
				tmp=tmp-b[(i+j+1)%n]+a[j];//两种表示一样的，移项就可以啦，这一种好理解
				//tmp-=(b[(i+j+1)%n]-a[j]);
				b[(i+j+1)%n]=a[j];
			}
		}
		ans=min(ans,tmp+(i+1)*x);//（i+1）代表进化次数
	}
	cout << ans << endl;
	return 0;
}

优先队列：

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int MAX = 2222;
priority_queue<ll,vector<ll>,greater<ll> > p[MAX];
ll a[MAX];
int main(){
	ll ans=0;
	ll n,x;
	cin >> n >> x;
	for (int i = 0; i < n;i++){
		cin >> a[i];
		ans+=a[i];//没采取进化的时候，得到所有类型所需的总金币
		p[i].push(a[i]);
	}
	ll tmp;
	for (int i = 0; i < n;i++){
		tmp=0;
		for (int j = 0; j < n;j++){
			p[j].push(a[(j-i+n)%n]);//求区间最小值的方法
			tmp+=p[j].top();
		}
		ans=min(ans,i*x+tmp);//i代表进化次数，i从0，是因为优先队列是从区间长度为1，开始的，也就是没采取进化措施~~
	}
	cout << ans << endl;
	return 0;
}