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