2017-6-7

題目描述

給你一群數字，在最大最小差值不大于17的情況下求出最小的花銷

解答

枚舉在中間值的所有的情況

代碼

/* ID: 18795871 PROG: skidesign LANG: C++ */ #include<iostream> #include<algorithm> #include<fstream> using namespace std;const int N = 1000; int x[N+1],n;ifstream fin("skidesign.in"); ofstream fout("skidesign.out");int res(int t){int s=0;for (int i=1;i<=n;i++){if (x[i]<t&&t-x[i]>8) s+=(t-x[i]-8)*(t-x[i]-8);else if (x[i]>t&&x[i]-t>9) s+=(x[i]-t-9)*(x[i]-t-9);}return s; }int main() {int r=0x3f3f3f3f;fin>>n;for (int i=1;i<=n;i++){fin>>x[i];}sort(x+1,x+n);if (x[n]-x[1]<=17) fout<<"0"<<endl;else{for (int i=8;i<=N-9;i++){r=min(res(i),r);}fout<<r<<endl;}return 0; }

一開始我還在想要不要怎么怎么樣，后來我發現，只要將所有情況枚舉出來就好，算出它們需要的開銷，然后求出最小值即可。
我是以左端點作為枚舉的目標的，那么它的范圍為最小值到最大值-17這個范圍區間。

/* ID: 18795871 PROG: skidesign LANG: C++ */ #include<iostream> #include<algorithm> #include<fstream> #define inf 0x3f3f3f3f using namespace std;ifstream fin("skidesign.in"); ofstream fout("skidesign.out");const int N = 1000; int x[N+1]; int n;int main(){while (fin>>n){for (int i=0;i<n;i++){fin>>x[i];}sort(x,x+n);int s,res=inf,m;for (int i=x[0];i<=x[n-1]-17;i++){s=0;for (int j=0;j<n;j++){if (x[j]>=i&&x[j]-i<=17) continue;m=min((x[j]-i)*(x[j]-i),(x[j]-i-17)*(x[j]-i-17));s+=m;}res=min(res,s);} fout<<res<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的USACO-Section1.4 Ski Course Design （枚举）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。