题解:NOI2016国王饮水记

庆祝通过noip2018初赛,系列五题EP2.

题目描述

跳蚤国有 n 个城市,伟大的跳蚤国王居住在跳蚤国首都中,即 1号城市中。

跳蚤国最大的问题就是饮水问题,由于首都中居住的跳蚤实在太多,跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用,这导致跳蚤国王也经常喝不上水。

于是,跳蚤国在每个城市都修建了一个圆柱形水箱,这些水箱完全相同且足够高。一个雨天后,第 i个城市收集到了高度为 hi 的水。由于地理和天气因素的影响,任何两个不同城市收集到的水高度互不相同。

跳蚤国王也请来蚂蚁工匠帮忙,建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时,可以指定任意多的城市,将这些城市的水箱用地下连通系统连接起来足够长的时间之后,再将地下连通系统关闭。由连通器原理,这些城市的水箱中的水在这次操作后会到达同一高度,并且这一高度等于指定的各水箱高度的平均值。

由于地下连通系统的复杂性,跳蚤国王至多只能使用 k次地下连通系统。跳蚤国王请你告诉他,首都 1号城市水箱中的水位最高能有多高?

输入输出格式

输入格式:

输入的第一行包含 3个正整数 n,k,p,分别表示跳蚤国中城市的数量,跳蚤国王能使用地下连通系统的最多次数,以及你输出的答案要求的精度。p 的含义将在输出格式中解释。

接下来一行包含 n个正整数,描述城市的水箱在雨后的水位。其中第 i 个 正整数 hi表示第 i 个城市的水箱的水位。保证 hi 互不相同,1le h_i le10^51hi105。

输出格式:

输出仅一行一个实数,表示 1 号城市的水箱中的最高水位。

这个实数只可以包含非负整数部分、小数点和小数部分。其中非负整数部分为必需部分,不加正负号。若有小数部分,则非负整数部分与小数部分之间以一个小数点隔开。若无小数部分,则不加小数点。

你输出的实数在小数点后不能超过 2p 位,建议保留至少 p位。数据保证参考答案与真实答案的绝对误差小于 10^{-2p}102p。

你的输出被判定为正确当且仅当你的输出与参考答案的绝对误差小于 $10^{−p}$。此外,每个测试点你将有可能获得部分分。

如果你的输出与参考答案的绝对误差不小于 10^{-p}10p 但小于 10^{-5}105,你可以获得该测试点 40% 的分数。

输入输出样例

输入样例#1: 复制
3 1 3
1 4 3
输出样例#1: 复制
2.666667

说明

由于至多使用一次地下连通系统,有以下 5 种方案:

  1. 不使用地下连通系统:此时 1 号城市的水箱水位为 1。

  2. 使用一次连通系统,连通 1、2 号:此时 11 号城市的水箱水位为 5/2。

  3. 使用一次连通系统,连通 1、3 号:此时 1 号城市的水箱水位为 2/2。

  4. 使用一次连通系统,连通 2、3号:此时 1 号城市的水箱水位为 1。

  5. 使用一次连通系统,连通 1、2、3号:此时 11 号城市的水箱水位为 8/3。

为保证答案精度,我们一般需要尽可能地在运算过程中保留超过 p位小数。我们可以证明,在各个子任务的参考算法中都能保证,在任何时候始终保留 6/5p位小数时,对任何输入得到的输出,与参考答案的绝对误差都小于 10^−p。

为了方便选手处理高精度小数,我们提供了定点高精度小数类。选手可以根据自己的需要参考与使用该类,也可以不使用该类。其具体的使用方法请参考下发的文档 decimal.pdf。

解题思路:

经过一系列推导之后可以发现这就是一个dp+斜率优化,但是高精度小数需要使用他给的板子(于是代码长度就超过了上一篇冰雪小屋)

(庆祝通过noip2018提高组初赛的第二题)

下面上代码:

  1#include<bits/stdc++.h>
2#define N 8005  
3using namespace std;
4int a[N],sum[N],pre[N][20],q[N*2];
5double dp[N][20];
6int n,k,p,st,lim,kk,l,r;
7double x;
8
9
10// ---------- decimal lib start ----------
11
12const int PREC = 3332;
13
14class Decimal {
15    public:
16        Decimal();
17        Decimal(const std::string &s);
18        Decimal(const char *s);
19        Decimal(int x);
20        Decimal(long long x);
21        Decimal(double x);
22
23        bool is_zero() const;
24
25        // p (p > 0) is the number of digits after the decimal point
26        std::string to_string(int p) const;
27        double to_double() const;
28
29        friend Decimal operator + (const Decimal &a, const Decimal &b);
30        friend Decimal operator + (const Decimal &a, int x);
31        friend Decimal operator + (int x, const Decimal &a);
32        friend Decimal operator + (const Decimal &a, long long x);
33        friend Decimal operator + (long long x, const Decimal &a);
34        friend Decimal operator + (const Decimal &a, double x);
35        friend Decimal operator + (double x, const Decimal &a);
36
37        friend Decimal operator - (const Decimal &a, const Decimal &b);
38        friend Decimal operator - (const Decimal &a, int x);
39        friend Decimal operator - (int x, const Decimal &a);
40        friend Decimal operator - (const Decimal &a, long long x);
41        friend Decimal operator - (long long x, const Decimal &a);
42        friend Decimal operator - (const Decimal &a, double x);
43        friend Decimal operator - (double x, const Decimal &a);
44
45        friend Decimal operator * (const Decimal &a, int x);
46        friend Decimal operator * (int x, const Decimal &a);
47
48        friend Decimal operator / (const Decimal &a, int x);
49
50        friend bool operator < (const Decimal &a, const Decimal &b);
51        friend bool operator > (const Decimal &a, const Decimal &b);
52        friend bool operator <= (const Decimal &a, const Decimal &b);
53        friend bool operator >= (const Decimal &a, const Decimal &b);
54        friend bool operator == (const Decimal &a, const Decimal &b);
55        friend bool operator != (const Decimal &a, const Decimal &b);
56
57        Decimal & operator += (int x);
58        Decimal & operator += (long long x);
59        Decimal & operator += (double x);
60        Decimal & operator += (const Decimal &b);
61
62        Decimal & operator -= (int x);
63        Decimal & operator -= (long long x);
64        Decimal & operator -= (double x);
65        Decimal & operator -= (const Decimal &b);
66
67        Decimal & operator *= (int x);
68
69        Decimal & operator /= (int x);
70
71        friend Decimal operator - (const Decimal &a);
72
73        // These can't be called
74        friend Decimal operator * (const Decimal &a, double x);
75        friend Decimal operator * (double x, const Decimal &a);
76        friend Decimal operator / (const Decimal &a, double x);
77        Decimal & operator *= (double x);
78        Decimal & operator /= (double x);
79
80    private:
81        static const int len = PREC / 9 + 1;
82        static const int mo = 1000000000;
83
84        static void append_to_string(std::string &s, long long x);
85
86        bool is_neg;
87        long long integer;
88        int data[len];
89
90        void init_zero();
91        void init(const char *s);
92};
93
94Decimal::Decimal() {
95    this->init_zero();
96}
97
98Decimal::Decimal(const char *s) {
99    this->init(s);
100}
101
102Decimal::Decimal(const std::string &s) {
103    this->init(s.c_str());
104}
105
106Decimal::Decimal(int x) {
107    this->init_zero();
108
109    if (x < 0) {
110        is_neg = true;
111        x = -x;
112    }
113
114    integer = x;
115}
116
117Decimal::Decimal(long long x) {
118    this->init_zero();
119
120    if (x < 0) {
121        is_neg = true;
122        x = -x;
123    }
124
125    integer = x;
126}
127
128Decimal::Decimal(double x) {
129    this->init_zero();
130
131    if (x < 0) {
132        is_neg = true;
133        x = -x;
134    }
135
136    integer = (long long)x;
137    x -= integer;
138
139    for (int i = 0; i < len; i++) {
140        x *= mo;
141        if (x < 0) x = 0;
142        data[i] = (int)x;
143        x -= data[i];
144    }
145}
146
147void Decimal::init_zero() {
148    is_neg = false;
149    integer = 0;
150    memset(data, 0, len * sizeof(int));
151}
152
153bool Decimal::is_zero() const {
154    if (integer) return false;
155    for (int i = 0; i < len; i++) {
156        if (data[i]) return false;
157    }
158    return true;
159}
160
161void Decimal::init(const char *s) {
162    this->init_zero();
163
164    is_neg = false;
165    integer = 0;
166
167    // find the first digit or the negative sign
168    while (*s != 0) {
169        if (*s == '-') {
170            is_neg = true;
171            ++s;
172            break;
173        } else if (*s >= 48 && *s <= 57) {
174            break;
175        }
176        ++s;
177    }
178
179    // read the integer part
180    while (*s >= 48 && *s <= 57) {
181        integer = integer * 10 + *s - 48;
182        ++s;
183    }
184
185    // read the decimal part
186    if (*s == '.') {
187        int pos = 0;
188        int x = mo / 10;
189
190        ++s;
191        while (pos < len && *s >= 48 && *s <= 57) {
192            data[pos] += (*s - 48) * x;
193            ++s;
194            x /= 10;
195            if (x == 0) {
196                ++pos;
197                x = mo / 10;
198            }
199        }
200    }
201}
202
203void Decimal::append_to_string(std::string &s, long long x) {
204    if (x == 0) {
205        s.append(148);
206        return;
207    }
208
209    char _[30];
210    int cnt = 0;
211    while (x) {
212        _[cnt++] = x % 10;
213        x /= 10;
214    }
215    while (cnt--) {
216        s.append(1, _[cnt] + 48);
217    }
218}
219
220std::string Decimal::to_string(int p) const {
221    std::string ret;
222
223    if (is_neg && !this->is_zero()) {
224        ret = "-";
225    }
226
227    append_to_string(ret, this->integer);
228
229    ret.append(1'.');
230
231    for (int i = 0; i < len; i++) {
232        // append data[i] as "%09d"
233        int x = mo / 10;
234        int tmp = data[i];
235        while (x) {
236            ret.append(148 + tmp / x);
237            tmp %= x;
238            x /= 10;
239            if (--p == 0) {
240                break;
241            }
242        }
243        if (p == 0break;
244    }
245
246    if (p > 0) {
247        ret.append(p, '0');
248    }
249
250    return ret;
251}
252
253double Decimal::to_double() const {
254    double ret = integer;
255
256    double k = 1.0;
257    for (int i = 0; i < len; i++) {
258        k /= mo;
259        ret += k * data[i];
260    }
261
262    if (is_neg) {
263        ret = -ret;
264    }
265
266    return ret;
267}
268
269bool operator < (const Decimal &a, const Decimal &b) {
270    if (a.is_neg != b.is_neg) {
271        return a.is_neg && (!a.is_zero() || !b.is_zero());
272    } else if (!a.is_neg) {
273        // a, b >= 0
274        if (a.integer != b.integer) {
275            return a.integer < b.integer;
276        }
277        for (int i = 0; i < Decimal::len; i++) {
278            if (a.data[i] != b.data[i]) {
279                return a.data[i] < b.data[i];
280            }
281        }
282        return false;
283    } else {
284        // a, b <= 0
285        if (a.integer != b.integer) {
286            return a.integer > b.integer;
287        }
288        for (int i = 0; i < Decimal::len; i++) {
289            if (a.data[i] != b.data[i]) {
290                return a.data[i] > b.data[i];
291            }
292        }
293        return false;
294    }
295}
296
297bool operator > (const Decimal &a, const Decimal &b) {
298    if (a.is_neg != b.is_neg) {
299        return !a.is_neg && (!a.is_zero() || !b.is_zero());
300    } else if (!a.is_neg) {
301        // a, b >= 0
302        if (a.integer != b.integer) {
303            return a.integer > b.integer;
304        }
305        for (int i = 0; i < Decimal::len; i++) {
306            if (a.data[i] != b.data[i]) {
307                return a.data[i] > b.data[i];
308            }
309        }
310        return false;
311    } else {
312        // a, b <= 0
313        if (a.integer != b.integer) {
314            return a.integer < b.integer;
315        }
316        for (int i = 0; i < Decimal::len; i++) {
317            if (a.data[i] != b.data[i]) {
318                return a.data[i] < b.data[i];
319            }
320        }
321        return false;
322    }
323}
324
325bool operator <= (const Decimal &a, const Decimal &b) {
326    if (a.is_neg != b.is_neg) {
327        return a.is_neg || (a.is_zero() && b.is_zero());
328    } else if (!a.is_neg) {
329        // a, b >= 0
330        if (a.integer != b.integer) {
331            return a.integer < b.integer;
332        }
333        for (int i = 0; i < Decimal::len; i++) {
334            if (a.data[i] != b.data[i]) {
335                return a.data[i] < b.data[i];
336            }
337        }
338        return true;
339    } else {
340        // a, b <= 0
341        if (a.integer != b.integer) {
342            return a.integer > b.integer;
343        }
344        for (int i = 0; i < Decimal::len; i++) {
345            if (a.data[i] != b.data[i]) {
346                return a.data[i] > b.data[i];
347            }
348        }
349        return true;
350    }
351}
352
353bool operator >= (const Decimal &a, const Decimal &b) {
354    if (a.is_neg != b.is_neg) {
355        return !a.is_neg || (a.is_zero() && b.is_zero());
356    } else if (!a.is_neg) {
357        // a, b >= 0
358        if (a.integer != b.integer) {
359            return a.integer > b.integer;
360        }
361        for (int i = 0; i < Decimal::len; i++) {
362            if (a.data[i] != b.data[i]) {
363                return a.data[i] > b.data[i];
364            }
365        }
366        return true;
367    } else {
368        // a, b <= 0
369        if (a.integer != b.integer) {
370            return a.integer < b.integer;
371        }
372        for (int i = 0; i < Decimal::len; i++) {
373            if (a.data[i] != b.data[i]) {
374                return a.data[i] < b.data[i];
375            }
376        }
377        return true;
378    }
379}
380
381bool operator == (const Decimal &a, const Decimal &b) {
382    if (a.is_zero() && b.is_zero()) return true;
383    if (a.is_neg != b.is_neg) return false;
384    if (a.integer != b.integer) return false;
385    for (int i = 0; i < Decimal::len; i++) {
386        if (a.data[i] != b.data[i]) return false;
387    }
388    return true;
389}
390
391bool operator != (const Decimal &a, const Decimal &b) {
392    return !(a == b);
393}
394
395Decimal & Decimal::operator += (long long x) {
396    if (!is_neg) {
397        if (integer + x >= 0) {
398            integer += x;
399        } else {
400            bool last = false;
401            for (int i = len - 1; i >= 0; i--) {
402                if (last || data[i]) {
403                    data[i] = mo - data[i] - last;
404                    last = true;
405                } else {
406                    last = false;
407                }
408            }
409            integer = -x - integer - last;
410            is_neg = true;
411        }
412    } else {
413        if (integer - x >= 0) {
414            integer -= x;
415        } else {
416            bool last = false;
417            for (int i = len - 1; i >= 0; i--) {
418                if (last || data[i]) {
419                    data[i] = mo - data[i] - last;
420                    last = true;
421                } else {
422                    last = false;
423                }
424            }
425            integer = x - integer - last;
426            is_neg = false;
427        }
428    }
429    return *this;
430}
431
432Decimal & Decimal::operator += (int x) {
433    return *this += (long long)x;
434}
435
436Decimal & Decimal::operator -= (int x) {
437    return *this += (long long)-x;
438}
439
440Decimal & Decimal::operator -= (long long x) {
441    return *this += -x;
442}
443
444Decimal & Decimal::operator /= (int x) {
445    if (x < 0) {
446        is_neg ^= 1;
447        x = -x;
448    }
449
450    int last = integer % x;
451    integer /= x;
452
453    for (int i = 0; i < len; i++) {
454        long long tmp = 1LL * last * mo + data[i];
455        data[i] = tmp / x;
456        last = tmp - 1LL * data[i] * x;
457    }
458
459    if (is_neg && integer == 0) {
460        int i;
461        for (i = 0; i < len; i++) {
462            if (data[i] != 0) {
463                break;
464            }
465        }
466        if (i == len) {
467            is_neg = false;
468        }
469    }
470
471    return *this;
472}
473
474Decimal & Decimal::operator *= (int x) {
475    if (x < 0) {
476        is_neg ^= 1;
477        x = -x;
478    } else if (x == 0) {
479        init_zero();
480        return *this;
481    }
482
483    int last = 0;
484    for (int i = len - 1; i >= 0; i--) {
485        long long tmp = 1LL * data[i] * x + last;
486        last = tmp / mo;
487        data[i] = tmp - 1LL * last * mo;
488    }
489    integer = integer * x + last;
490
491    return *this;
492}
493
494Decimal operator - (const Decimal &a) {
495    Decimal ret = a;
496    // -0 = 0
497    if (!ret.is_neg && ret.integer == 0) {
498        int i;
499        for (i = 0; i < Decimal::len; i++) {
500            if (ret.data[i] != 0break;
501        }
502        if (i < Decimal::len) {
503            ret.is_neg = true;
504        }
505    } else {
506        ret.is_neg ^= 1;
507    }
508    return ret;
509}
510
511Decimal operator + (const Decimal &a, int x) {
512    Decimal ret = a;
513    return ret += x;
514}
515
516Decimal operator + (int x, const Decimal &a) {
517    Decimal ret = a;
518    return ret += x;
519}
520
521Decimal operator + (const Decimal &a, long long x) {
522    Decimal ret = a;
523    return ret += x;
524}
525
526Decimal operator + (long long x, const Decimal &a) {
527    Decimal ret = a;
528    return ret += x;
529}
530
531Decimal operator - (const Decimal &a, int x) {
532    Decimal ret = a;
533    return ret -= x;
534}
535
536Decimal operator - (int x, const Decimal &a) {
537    return -(a - x);
538}
539
540Decimal operator - (const Decimal &a, long long x) {
541    Decimal ret = a;
542    return ret -= x;
543}
544
545Decimal operator - (long long x, const Decimal &a) {
546    return -(a - x);
547}
548
549Decimal operator * (const Decimal &a, int x) {
550    Decimal ret = a;
551    return ret *= x;
552}
553
554Decimal operator * (int x, const Decimal &a) {
555    Decimal ret = a;
556    return ret *= x;
557}
558
559Decimal operator / (const Decimal &a, int x) {
560    Decimal ret = a;
561    return ret /= x;
562}
563
564Decimal operator + (const Decimal &a, const Decimal &b) {
565    if (a.is_neg == b.is_neg) {
566        Decimal ret = a;
567        bool last = false;
568        for (int i = Decimal::len - 1; i >= 0; i--) {
569            ret.data[i] += b.data[i] + last;
570            if (ret.data[i] >= Decimal::mo) {
571                ret.data[i] -= Decimal::mo;
572                last = true;
573            } else {
574                last = false;
575            }
576        }
577        ret.integer += b.integer + last;
578        return ret;
579    } else if (!a.is_neg) {
580        // a - |b|
581        return a - -b;
582    } else {
583        // b - |a|
584        return b - -a;
585    }
586}
587
588Decimal operator - (const Decimal &a, const Decimal &b) {
589    if (!a.is_neg && !b.is_neg) {
590        if (a >= b) {
591            Decimal ret = a;
592            bool last = false;
593            for (int i = Decimal::len - 1; i >= 0; i--) {
594                ret.data[i] -= b.data[i] + last;
595                if (ret.data[i] < 0) {
596                    ret.data[i] += Decimal::mo;
597                    last = true;
598                } else {
599                    last = false;
600                }
601            }
602            ret.integer -= b.integer + last;
603            return ret;
604        } else {
605            Decimal ret = b;
606            bool last = false;
607            for (int i = Decimal::len - 1; i >= 0; i--) {
608                ret.data[i] -= a.data[i] + last;
609                if (ret.data[i] < 0) {
610                    ret.data[i] += Decimal::mo;
611                    last = true;
612                } else {
613                    last = false;
614                }
615            }
616            ret.integer -= a.integer + last;
617            ret.is_neg = true;
618            return ret;
619        }
620    } else if (a.is_neg && b.is_neg) {
621        // a - b = (-b) - (-a)
622        return -b - -a;
623    } else if (a.is_neg) {
624        // -|a| - b
625        return -(-a + b);
626    } else {
627        // a - -|b|
628        return a + -b;
629    }
630}
631
632Decimal operator + (const Decimal &a, double x) {
633    return a + Decimal(x);
634}
635
636Decimal operator + (double x, const Decimal &a) {
637    return Decimal(x) + a;
638}
639
640Decimal operator - (const Decimal &a, double x) {
641    return a - Decimal(x);
642}
643
644Decimal operator - (double x, const Decimal &a) {
645    return Decimal(x) - a;
646}
647
648Decimal & Decimal::operator += (double x) {
649    *this = *this + Decimal(x);
650    return *this;
651}
652
653Decimal & Decimal::operator -= (double x) {
654    *this = *this - Decimal(x);
655    return *this;
656}
657
658Decimal & Decimal::operator += (const Decimal &b) {
659    *this = *this + b;
660    return *this;
661}
662
663Decimal & Decimal::operator -= (const Decimal &b) {
664    *this = *this - b;
665    return *this;
666}
667
668// ---------- decimal lib end ----------
669
670
671void read(){
672    scanf("%d%d%d",&n,&k,&p);
673    kk=k;
674    cin >> a[1];
675    for (int i=2;i<=n;i++)
676        scanf("%d",&a[i]);
677    sort(a+2,a+1+n);
678    for (int i=2;i<=n;i++)
679        if (a[i]>a[1]){
680            st=i;
681            break;
682        }
683    for (int i=1;i<=(n-st+1);i++)
684        a[i+1]=a[i+st-1];
685    n=n-st+2;
686    for (int i=1;i<=n;i++)
687        sum[i]=sum[i-1]+a[i];
688    for (int i=1;i<=n;i++)
689        dp[i][0]=a[1];
690    lim=min(n,k);
691    lim=min(lim,14);
692//    cout << n << "         nnnnn    nnn " <<  endl;
693//    for (int i=1;i<=3;i++)
694//        cout << a[i] << "  ";
695//    cout << "     a     aaaaaaaa    aaa " <<  endl; 
696}
697double X(int x){
698    return x;
699
700double Y(int j,int y){
701    return sum[y]-dp[y][j-1];
702}
703double slope(int j,int x,int y){
704    return (Y(j,x)-Y(j,y))/(X(x)-X(y));
705}
706double slope1(int i,int j,int x,int y){
707    double res;
708    res=((Y(j,x)-Y(j,y))/(sum[i]-sum[x]+dp[x][j-1]));
709    return res;
710
711Decimal getans(int i,int j){
712    if (j==0return a[1];
713    return (getans(pre[i][j],j-1)+sum[i]-sum[pre[i][j]])/(i-pre[i][j]+1);
714}
715double f(int i,int j){
716    return sum[i]-dp[i][j];
717}
718void solve(){
719    q[0]=1;
720    for (int j=1;j<=lim;j++){
721        l=r=0;
722        for (int i=2;i<=n;i++){
723//            while (l<r && slope1(i,j,q[l],q[l+1])>=(q[l]-q[l+1])/(i-q[l]+1) ) l++;
724            while (l<r && 1.0*(q[l]-q[l+1])/(i-q[l]+1)<=(f(q[l],j-1)-f(q[l+1],j-1))/(sum[i]-f(q[l],j-1))) l++;
725            int k=q[l];
726            dp[i][j]=(dp[k][j-1]+sum[i]-sum[k])/(i-k+1);
727            pre[i][j]=k; 
728            while (l<r && slope(j,q[r-1],q[r])>=slope(j,q[r],i)) r--;
729            q[++r]=i;
730        }
731    }
732    int mx=0,m=n-kk+lim; if (m<2)m=2;
733    for (int i=0;i<=lim;i++)
734        if (dp[m][i]>dp[m][mx]) mx=i;
735
736    Decimal ans;
737    ans=getans(m,mx);
738    for (int i=m+1;i<=n;i++)
739        ans=(ans+a[i])/2;
740    std::cout << ans.to_string((p<<1)<=3500?p<<1:3500) << std::endl
741}
742int main(){
743//    freopen("1721-1.in","r",stdin);
744    read();
745    solve();
746    return 0;
747}
原文地址:https://www.cnblogs.com/titititing/p/9822528.html