首页 > 代码库 > hdu5073 简单枚举+精度处理
hdu5073 简单枚举+精度处理
其实这题还是挺简单的，因为移动k个星球后，这k个星球的权值就可以变为0，所以只有剩下的本来就是连着的才是最优解，也就是说要动也是动两端的，那么就O(N)枚举一遍动哪些就好了。
我是在杭电oj题目重现的比赛上做这题，因为之前听人说现场赛时有人用n^2的算法蹭过了，所以我不断蹭，蹭了一个小时都没蹭过。。。~！@#￥%……
先贴一份乱七八糟想蹭过的代码
/* * Author : ben */#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>#include <stack>#include <string>#include <vector>#include <deque>#include <list>#include <functional>#include <numeric>#include <cctype>using namespace std;typedef long long LL;const double eps = 1e-9;int get_int() { int res = 0, ch; while (!((ch = getchar()) >= ‘0‘ && ch <= ‘9‘)) { if (ch == EOF) return 1 << 30; } res = ch - ‘0‘; while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) res = res * 10 + (ch - ‘0‘); return res;}//输入整数(包括负整数)，用法int a = get_int2();int get_int2() { int res = 0, ch, flag = 0; while (!((ch = getchar()) >= ‘0‘ && ch <= ‘9‘)) { if (ch == ‘-‘) flag = 1; if (ch == EOF) return 1 << 30; } res = ch - ‘0‘; while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) res = res * 10 + (ch - ‘0‘); if (flag == 1) res = -res; return res;}const int MAXN = 50100;int N, K, data[MAXN];int ndata[MAXN];LL sum[MAXN];double ans;inline double getCenter(int s, int e) { LL su = sum[e]; if (s > 0) { su -= sum[s - 1]; } double ret = su / (e - s + 1.0); return ret;}void comput(int s, int e, double c) { double ret = 0; for (int i = s; i <= e; i++) { ret += (data[i] - c) * (data[i] - c); if (ret > ans) { return; } } if (ret < ans) { ans = ret; }}double comput(double c) { double ret = 0; for (int i = 0; i < N; ) { ret += (data[i] - c) * (data[i] - c) * ndata[i]; i += ndata[i]; } return ret;}void work() { double cen = getCenter(0, N - 1);// printf("cen = %f\n", cen); ans = comput(cen); for (int a = K; a >= 0; a--) { if (ans < eps) { break; } int e = N + a - K - 1; double tmpc = getCenter(a, e); comput(a, e, tmpc); }}void treat() { for (int i = 0; i < N; i++) { int d = data[i]; int j = i + 1; while (j < N && data[j] == d) { j++; } int num = j - i; for (j--; j >= i; j--) { ndata[j] = num - j + i; } }}int main() { int T = get_int(); while (T--) { N = get_int(); K = get_int(); for (int i = 0; i < N; i++) { data[i] = get_int2(); } sort(data, data + N); treat(); sum[0] = data[0]; for (int i = 1; i < N; i++) { sum[i] = sum[i - 1] + data[i]; } work(); printf("%.10lf\n", ans); } return 0;}
下面是正常做法，其实相对于上面的代码也就只有一处改进，因为上面那份代码求解(xi-x)^2的时候是依次计算累加的，可以通过展开公式，通过预存前n项平方和的方式来计算，把这个计算过程从O(N)变成O(1)，就可以过了。
不过我还是wa了几发，原因是一开始忘了对N==K和N-1==K的情况作特殊处理了，因为我后面的代码这个地方没单独考虑。
1 /* 2 * Author : ben 3 */ 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <cmath> 8 #include <ctime> 9 #include <iostream> 10 #include <algorithm> 11 #include <queue> 12 #include <set> 13 #include <map> 14 #include <stack> 15 #include <string> 16 #include <vector> 17 #include <deque> 18 #include <list> 19 #include <functional> 20 #include <cctype> 21 using namespace std; 22 typedef long long LL; 23 const double eps = 1e-9; 24 const int MAXN = 50100; 25 int N, K; 26 LL data[MAXN], sum[MAXN], sum2[MAXN]; 27 double ans; 28 int get_int() { 29 int res = 0, ch; 30 while (!((ch = getchar()) >= ‘0‘ && ch <= ‘9‘)) { 31 if (ch == EOF) 32 return 1 << 30; 33 } 34 res = ch - ‘0‘; 35 while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) 36 res = res * 10 + (ch - ‘0‘); 37 return res; 38 } 39 40 //输入整数(包括负整数)，用法int a = get_int2(); 41 int get_int2() { 42 int res = 0, ch, flag = 0; 43 while (!((ch = getchar()) >= ‘0‘ && ch <= ‘9‘)) { 44 if (ch == ‘-‘) 45 flag = 1; 46 if (ch == EOF) 47 return 1 << 30; 48 } 49 res = ch - ‘0‘; 50 while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) 51 res = res * 10 + (ch - ‘0‘); 52 if (flag == 1) 53 res = -res; 54 return res; 55 } 56 inline LL getSum(int from, int to) { 57 LL ret = sum[to]; 58 if (from > 0) { 59 ret -= sum[from - 1]; 60 } 61 return ret; 62 } 63 64 inline LL getSum2(int from, int to) { 65 LL ret = sum2[to]; 66 if (from > 0) { 67 ret -= sum2[from - 1]; 68 } 69 return ret; 70 } 71 72 inline double getCenter(int s, int e) { 73 LL su = sum[e]; 74 if (s > 0) { 75 su -= sum[s - 1]; 76 } 77 double ret = su / (e - s + 1.0); 78 return ret; 79 } 80 81 inline double comput(int s, int e, double c) { 82 LL s1 = getSum(s, e); 83 LL s2 = getSum2(s, e); 84 double ret = s2 + (e - s + 1.0) * c * c - 2.0 * c * s1; 85 return ret; 86 } 87 88 void work() { 89 double cen = getCenter(0, N - 1); 90 ans = comput(0, N - 1, cen); 91 for (int a = 0; a <= K; a++) { 92 int e = N + a - K - 1; 93 double tmpc = getCenter(a, e); 94 double ret = comput(a, e, tmpc); 95 if (ret < ans) { 96 ans = ret; 97 } 98 } 99 }100 101 int main() {102 #ifndef ONLINE_JUDGE103 freopen("data.in", "r", stdin);104 #endif105 int T= get_int();106 while (T--) {107 N = get_int();108 K = get_int();109 for (int i = 0; i < N; i++) {110 data[i] = get_int2();111 }112 if (K == N || N - 1 == K) {113 printf("0\n");114 continue;115 }116 sort(data, data + N);117 sum[0] = data[0];118 sum2[0] = data[0] * data[0];119 for (int i = 1; i < N; i++) {120 sum[i] = sum[i - 1] + data[i];121 sum2[i] = sum2[i - 1] + data[i] * data[i];122 }123 work();124 printf("%.10lf\n", ans);125 }126 return 0;127 }
hdu5073 简单枚举+精度处理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。