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;
}