P3137 [USACO16FEB] Circular Barn S

P3137 [USACO16FEB] Circular Barn S

思路：数据范围为O(n^2)那么因此我们可以暴力，那么如何进行构造呢？首先假设一头奶牛在a，一头在b，如果要使一个到b，另一个到c，（a<b<c)，那肯定选择a的奶牛到b，b的奶牛到c的花费更小，那么我们可以保证每个地方必然有一个奶牛要移动，可以用优先队列存，提取最前面的奶牛，然后计算最前面的奶牛到这个点的距离，那么起始点怎么判断？就可以考虑用暴力的写法一个个去枚举。最后计算最小答案即可。

代码：

#include <bits/stdc++.h>
#define int long long
#define fi first 
#define se second
#define all(v) v.begin(),v.end()
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f;
const int N = 5005;
int a[N];
int n;void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=n+1;i<=2*n;i++)a[i] = a[i-n];int ans = inf;priority_queue<int,vector<int>,greater<int>>q;for(int i=1;i<=n;i++){bool flag = true;int res = 0;for(int j=i;j<=i+n-1;j++){if(q.size() == 0 && a[j] == 0){flag = false;break;}int cnt = a[j];while(cnt--)q.push(j);int x = q.top();q.pop();res += (j-x)*(j-x);}if(!flag)continue;ans = min(ans,res);}cout<<ans<<"\n";}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;//cin>>T;while(T--){solve();}return 0;
}