首页 > 代码库 > HDU 4923 Room and Moor
HDU 4923 Room and Moor
题意:
给你一个A数列,让你求一个单调递增的B数列(0<=bi<=1),使得sum{(ai-bi)^2}最小。
思路:
很明显,如果A = 0...01...1,那么bi=ai即可。
可以证明,如果 A = 1...10...0,那么所有bi达到同一个值的时候取得最优值。 假设 ai = 1, aj = 0, 那么 i<j ,所以bi<=bj。 若bi != bj,那么增大bi的值,或者减小bj的值都可以得到更优的结果。 所以,bi=bj。
所以,如果A数列里面出现了形如 "1...10...0"的部分,我们都可以把它当做同一段处理。因为他们对应的bi值一定相同。
这样,我们可以得到一个中间序列,x1, ..., x1, x2, ..., x2, ..., xm, ...xm. 我们可以把它简化为,x1, ..., xm。其中 xi对应着每一段的最优值。
我们可以发现,这里的xi不一定单调递增。 然后我们仿照上面的证明,知道当有相邻两段的xi递减时,会在他们所有的bi相等时取得最优值。因此,我们可以把这两段合并,求出一个满足单调性的值。
所以,最后的B序列一定是这样:y1, ..., y1, ..., ym, ..., ym。所以我们可以用一个单调栈来维护所有的bi值。
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <time.h>15 16 using namespace std;17 18 typedef pair<double, int> PDI;19 20 const int INF = 1<<30;21 const int MAXN = (int) 1e5+7;22 23 int n;24 int a[MAXN];25 double b[MAXN];26 27 PDI sk[MAXN]; //栈28 int tail; //栈顶指针29 30 void solve() {31 tail = 0; //栈初始化32 33 for (int i = 0; i < n; i++) {34 sk[tail++] = make_pair(1.0*a[i], 1); //当前点入栈35 while (tail>1 && sk[tail-1].first<=sk[tail-2].first) { //如果栈不满足单调性,合并最上面两个节点36 int cnt = sk[tail-1].second+sk[tail-2].second;37 double tmp = (sk[tail-1].first*sk[tail-1].second+sk[tail-2].first*sk[tail-2].second)/cnt;38 sk[tail-2] = make_pair(tmp, cnt);39 tail--;40 }41 }42 //求出bi43 for (int i = 0, j = 0; i < tail; i++)44 for (int k = 0; k < sk[i].second; k++)45 b[j++] = sk[i].first;46 //求出结果47 double ans = 0;48 for (int i = 0; i < n; i++)49 ans += (a[i]-b[i])*(a[i]-b[i]);50 printf("%f\n", ans);51 }52 53 int main() {54 #ifdef Phantom0155 freopen("HDU4923.txt", "r", stdin);56 #endif //Phantom0157 58 int T;59 scanf("%d", &T);60 while (T--) {61 scanf("%d", &n);62 for (int i = 0; i < n; i++)63 scanf("%d", &a[i]);64 solve();65 }66 67 return 0;68 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。