首页 > 代码库 > 【USACO 1.3】Ski Course Design
【USACO 1.3】Ski Course Design
n个点(n<=1000)大小范围[0,100],改变一些点的值,使得极差不超过17,代价为改变值的平方。
枚举修改后的最低高度low,维护最小代价。
/*TASK: skidesignLANG:C++URL:http://train.usaco.org/usacoprob2?a=LxVrSLLAzuR&S=skidesign*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long long#define N 1005using namespace std;int n,h[N];int tol=0x3f3f3f3f;int sqr(int x){ return x*x;}int main() { freopen("skidesign.in","r",stdin); freopen("skidesign.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&h[i]); } sort(h+1,h+1+n); for(int low=h[1];low<=h[n]-17;low++){ int ans=0; for(int i=1;i<=n;i++){ if(h[i]<low)ans+=sqr(low-h[i]); else if(h[i]>low+17)ans+=sqr(h[i]-low-17); } tol=min(tol,ans); } printf("%d\n",tol);}
【USACO 1.3】Ski Course Design
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。