Home PAT 1125 Chain the Ropes
Post
Cancel

PAT 1125 Chain the Ropes

Link

越早加入绳子的段, 对折的次数就越多, 因此想让绳子最长就应该让长度较长的段对折次数尽可能少.

将所有段从小到大排序, 依次加入绳子中即可.

AC 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,a[10010],cur;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    cur=a[1];
    for(int i=2;i<=n;++i)
        cur=(cur+a[i])>>1;
    printf("%d\n",cur);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.

PAT 1158 Telefraud Detection

PAT 1123 Is It a Complete AVL Tree