本文主要是介绍肥猪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
小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
思路：
假设要取 i-2 这个地方的代价来填充 i 这个位置，那么在剩下两次右移时放入 i-2 这个位置即可，如果要用原来的价值，那么就等全部右移完再放入
因此，若已知共右移 x 次，那么每头猪的最小代价是确定的，即：
枚举右移的次数 k，对于每个 k 算出最小代价，然后使用线段树求区间最小值即可
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;struct Tree{LL l,r;LL minn;
}tree[N*2];
LL n,x;
LL a[N];
void Insert(LL root){LL lc=root<<1;LL rc=root<<1|1;tree[root].minn=min(tree[lc].minn,tree[rc].minn);
}
void build(LL l,LL r,LL root) {tree[root].l=l;tree[root].r=r;if(l==r) {tree[root].minn=a[l];return;}LL lc=root<<1;LL rc=root<<1|1;LL mid=(l+r)>>1;build(l,mid,lc);build(mid+1,r,rc);Insert(root);
}
LL query(LL L, LL R, LL root) {LL l=tree[root].l;LL r=tree[root].r;if(L<=l&&r<=R) {return tree[root].minn;}LL res=1E18;LL lc=root<<1;LL rc=root<<1|1;LL mid=(l+r)>>1;if(L<=mid)res=min(res,query(L,R,lc));if(R>mid)res=min(res,query(L,R,rc));return res;
}
int main() {scanf("%lld%lld",&n,&x);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,n,1);LL res=1E18;for(int k=0;k<=n;k++) {LL sum=k*x;for(int i=1;i<=n;i++) {if(i-k<1)sum+=min(query(1,i,1),query(n-k+i,n,1));elsesum+=query(i-k,i,1);}res=min(res,sum);}printf("%lld\n",res);return 0;
}
这篇关于肥猪的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
