网站管理规划方案,凡科网登录下载,老板网人才招聘,新手小白如何做电商P3137 [USACO16FEB] Circular Barn S
思路#xff1a;数据范围为O(n^2)那么因此我们可以暴力#xff0c;那么如何进行构造呢#xff1f;首先假设一头奶牛在a#xff0c;一头在b#xff0c;如果要使一个到b#xff0c;另一个到c#xff0c;#xff08;abc)数据范围为O(n^2)那么因此我们可以暴力那么如何进行构造呢首先假设一头奶牛在a一头在b如果要使一个到b另一个到cabc)那肯定选择a的奶牛到bb的奶牛到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(){cinn;for(int i1;in;i)cina[i];for(int in1;i2*n;i)a[i] a[i-n];int ans inf;priority_queueint,vectorint,greaterintq;for(int i1;in;i){bool flag true;int res 0;for(int ji;jin-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);}coutans\n;}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T 1;//cinT;while(T--){solve();}return 0;
}
