蓝桥杯2018A组复盘 | vegetable1024's Blog

概况

按照考试时间进行的一次复盘呢…

有点不理想，因为看错题白给了一道编程题，麻了…

不过出乎意外的填空题还可以？答案填空和代码填空都全对了说…

三维差分虽然想到了但是却没多少时间写了噢…

总的来说只能算是中下吧，还有很大进步空间…

$89/150$的成绩估计在$A$组是很难出线的呢…

感觉这次填空题比$2017A$要简单很多…

今天还有个别的烦心…在New Online Judge群里面见到一个错误的最大公约数求法，却因为OJ测试数据有点水被AC了…然后我造了一组数据把他卡了，好像是白费苦心呢，还被diss抬杠了，果然我还是管好自己比较好噢…

开始今天的题解！

题目

*表格来源于：https://blog.csdn.net/weixin_43914593/article/details/112505733

序号	标题	类型	分值	提交链接
1	分数	结果填空	5	http://oj.ecustacm.cn/problem.php?id=1359
2	星期一	结果填空	7	http://oj.ecustacm.cn/problem.php?id=1360
3	乘积尾零	结果填空	9	http://oj.ecustacm.cn/problem.php?id=1361
4	第几个幸运数	结果填空	13	http://oj.ecustacm.cn/problem.php?id=1362
5	打印图形	代码填空	11	无
6	航班时间	程序设计	17	http://oj.ecustacm.cn/problem.php?id=1363
7	三体攻击	程序设计	19	http://oj.ecustacm.cn/problem.php?id=1364
8	全球变暖	程序设计	21	http://oj.ecustacm.cn/problem.php?id=1365
9	倍数问题	程序设计	23	http://oj.ecustacm.cn/problem.php?id=1366
10	付账问题	程序设计	25	http://oj.ecustacm.cn/problem.php?id=1367

分数

答案：1048575/524288

本来是用程序写好了的，不过在写第二题的时候删了所以就无了。

主要思想是，先通分为$\frac{…}{2^{19}}$这样的形式，再对分子求和，最后化为最简分式问题，只需要求分子分母的$GCD$，然后除去就能得到答案。

当然，此题是一个等比数列相加求和的问题，因此可以用相关公式计算，辅以电脑计算器小程序来完成化简。

星期一

答案：5217

日历题？好像每年都有这种类型的题目。

主要思想是首先通过Windows的日历程序，确认2000.12.31是星期几，然后往前递推即可。

在递推过程中，需要特别处理闰年情况，跨年情况。

代码：

#include <bits/stdc++.h>
using namespace std;
int week[2005][15][35];
int mday[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int calc(int y, int m){
    if(m != 2)  return mday[m];
    return ((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0)) ? 29 : 28;
}
int calc2(int y, int m){
    if(m == 12)
        return week[y + 1][1][1] - 1;
    else
        return week[y][m + 1][1] - 1;
}
int main(void)
{
    week[2001][1][1] = 1;
    week[2000][12][31] = 0;
    for(int i = 2000; i >= 1901; i--)
        for(int j = 12; j >= 1; j--)
            for(int k = calc(i, j); k >= 1; k--)
            {
                if(k == calc(i, j))
                    week[i][j][k] = calc2(i, j);
                else
                    week[i][j][k] = week[i][j][k + 1] - 1;
                
                if(week[i][j][k] < 0)
                    week[i][j][k] += 7; 
                
                /*
                if(j == 1 && k == 1)
                    system("pause");

                printf("%d %d %d %d\n", i, j, k, week[i][j][k]);
                
                if(j == 12 && k == 31)
                    system("pause");
                */
            }
    int cnt = 0;
    for(int i = 2000; i >= 1901; i--)
        for(int j = 12; j >= 1; j--)
            for(int k = calc(i, j); k >= 1; k--)
                if(week[i][j][k] == 1)
                    cnt++;
    printf("%d\n", cnt);
    return 0;  
}

乘积尾零

答案：31

出现了很多次的考点。

统计尾巴的$0$，只需要统计有多少对$2$和$5$相乘。

因此在质因数分解中，统计$2$和$5$的因子数量，取两者的最小值即可。

#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int num[maxn];
void calc(int x){
    int r = x;
    for(int i = 2; i <= r; i++)
        while(x % i == 0)   
        {
            x /= i;
            num[i]++;
            //printf("debug: %d, %d\n", i, num[i]);
        }
}
signed main(void)
{
    srand(time(NULL));
    int res = 1;
    for(int i = 1; i <= 100; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        calc(tmp);
        res *= tmp;
    }
    printf("%lld %lld %lld\n", num[2], num[5], min(num[2], num[5]));
}

第几个幸运数

答案：1905

搜索题。

需要注意$long\ long$的溢出问题。

由于要考虑数字唯一，且数字有序，我们使用$set$来帮助我们存储计算幸运数。

最后计算$set$内的元素个数即可。

在我的代码中，$set$内的第一个元素是$1$，因此需要在计算出的元素个数上再减去一，就能得到答案。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
set<ll> s1;
void dfs(ll now){
    if(now > 59084709587505)    return;
    if(!s1.count(now))
    {
        s1.insert(now);
        dfs(now * 3LL);
        dfs(now * 5LL);
        dfs(now * 7LL);
    }
}
int main(void)
{
    dfs(1LL);
    printf("%lld\n", s1.size());
    for(set<ll>::iterator iter = s1.begin(); iter != s1.end(); iter++)
        printf("%lld ", *iter);
    return 0;
}

打印图形

答案：size / 3

代码填空题。

而且挖空挖的是一个递归，缩小规模的空。

这种时候我们分析大图形与小图形的大小关系即可，可以得到$1:3$的关系。

因此，填上size / 3到源代码中，然后在$IDE$里跑一下，发现确实如此，就可以到下一题了。

航班时间

这一题在New Online Judge的数据应该是在Windows下造的，换行符是\r\n，被坑了一下。

本题难点在于字符串处理。

我的方法比较暴力，因为只有一个数的时候会自动补上前导$0$，因此只需要$getline$读取，然后直接按位置提取数字就可以了。

跨越时间的计算问题，只要把$(+n)$变为$24*n$小时算到降落时间里面，再操作就好了。

而飞行时间的计算，根据两处起落时间可以列出一条二元一次方程，转载罗老师的$Blog$如下：

 设起飞时间是S，到达时间是E，单程飞行时间是X，时差是T。
 从A到B：S1+X+T=E1
 从B到A：S1+X-T=E2
 整理两式得：2X=(E1-S1) + (E2-S1)，答案就是X。
 可见，并不需要计算时差T，因为一去一回，互相抵消了。

代码：

#include <bits/stdc++.h>
using namespace std;
int t;
string str1, str2;
struct tim{
    int h;
    int m;
    int s;
}s1, t1, s2, t2;
int calc_s(tim now){
    return now.h * 3600 + now.m * 60 + now.s;
}
int fh(int rs){
    return rs / 3600;
}
int fm(int rs){
    return rs / 60 % 60;
}
int fs(int rs){
    return rs % 60;
}
int main(void)
{
    scanf("%d", &t); 
    //为了处理换行符不被getline吃了
    while(getchar() != '\n');
    while(t--)
    {

        getline(cin, str1);
        getline(cin, str2);
        
        s1.h = (str1[0] - '0') * 10 + (str1[1] - '0');
        s1.m = (str1[3] - '0') * 10 + (str1[4] - '0');
        s1.s = (str1[6] - '0') * 10 + (str1[7] - '0');
        
        t1.h = (str1[9] - '0') * 10 + (str1[10] - '0');
        t1.m = (str1[12] - '0') * 10 + (str1[13] - '0');
        t1.s = (str1[15] - '0') * 10 + (str1[16] - '0');

        if(str1.find("(") != string::npos)    t1.h += (str1[20] - '0') * 24;
        
        s2.h = (str2[0] - '0') * 10 + (str2[1] - '0');
        s2.m = (str2[3] - '0') * 10 + (str2[4] - '0');
        s2.s = (str2[6] - '0') * 10 + (str2[7] - '0');
        
        t2.h = (str2[9] - '0') * 10 + (str2[10] - '0');
        t2.m = (str2[12] - '0') * 10 + (str2[13] - '0');
        t2.s = (str2[15] - '0') * 10 + (str2[16] - '0');

        if(str2.find("(") != string::npos)    t2.h += (str2[20] - '0') * 24;

        /*
        printf("%d %d %d\n", s1.h, s1.m, s1.s);
        printf("%d %d %d\n", t1.h, t1.m, t1.s);
        printf("%d %d %d\n", s2.h, s2.m, s2.s);
        printf("%d %d %d\n", t2.h, t2.m, t2.s);
        */

        int rs = (calc_s(t1) + calc_s(t2) - calc_s(s1) - calc_s(s2)) / 2;
        printf("%02d:%02d:%02d\n", fh(rs), fm(rs), fs(rs));
    }
    return 0;
}

三体攻击

模拟比赛前做过类似题目，知道是三维差分+二分。不过忘了三维差分怎么写，当时也没有时间推，就只写了部分分。

最简单的部分分做法就是从第一次攻击开始模拟，直到出现战机坠落的那次为止。

代码：

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int A, B, C, m, hp[maxn];
struct At{
    int ht;
    int lat, rat, lbt, rbt, lct, rct;
} attack[maxn];
int main(void)
{
    scanf("%d %d %d %d", &A, &B, &C, &m);
    for(int i = 1; i <= A * B * C; i++)    scanf("%d", &hp[i]);
    for(int i = 1; i <= m; i++)
        scanf("%d %d %d %d %d %d %d", &attack[i].lat, &attack[i].rat, &attack[i].lbt, &attack[i].rbt, &attack[i].lct, &attack[i].rct, &attack[i].ht);
    int flag = 0;
    for(int now = 1; now <= m; now++)
    {
        for(int i = attack[now].lat; !flag && i <= attack[now].rat; i++)
        {
            for(int j = attack[now].lbt; !flag && j <= attack[now].rbt; j++)
            {
                for(int k = attack[now].lct; !flag && k <= attack[now].rct; k++)
                {
                    hp[((i - 1) * B + (j - 1)) * C + (k - 1) + 1] -= attack[now].ht;
                    if(hp[((i - 1) * B + (j - 1)) * C + (k - 1) + 1] < 0)
                    {
                        flag = now;
                        break;
                    }
                }
            }
        }
    }
    printf("%d\n", flag);
    return 0;
}

这份暴力代码也可以用于对拍三维差分，在很难一次写对的情况这样的对拍无疑能够安心很多。

赛后补充了三维差分的知识，画图如下：

可以发现+k和-k都是间隔排布的，我们可以利用这个规律，记住左下角$(x_1,y_1,z_1)$是+k的，然后顺势推导出其他情况。出现这样的情况本质上是因为容斥原理。也正是因为容斥，代码中会出现隐藏的二项式系数$1:3:3:1$，如下：

D[calc(nx1, ny1, nz1)] += dhp;

D[calc(nx1, ny1, nz2 + 1)] -= dhp;
D[calc(nx2 + 1, ny1, nz1)] -= dhp;
D[calc(nx1, ny2 + 1, nz1)] -= dhp;

D[calc(nx2 + 1, ny1, nz2 + 1)] += dhp;
D[calc(nx1, ny2 + 1, nz2 + 1)] += dhp;
D[calc(nx2 + 1, ny2 + 1, nz1)] += dhp;

D[calc(nx2 + 1, ny2 + 1, nz2 + 1)] -= dhp;

由此，再结合飞船血量的单调性（血量只会下降不会上升），进行二分，就可以完成该题。

还有一点需要特别注意，由于本题只给出了$A B C$的上限，没有给出$A,B,C$的上限，因此理想做法是压三维为一维，再写一个$d(i,j,k)$坐标转换到压维后数组下标的函数（需要特别注意是否存在越界问题）辅以计算。转化的式子题目中已经给出，照搬即可。

总的来说，这题是三维差分+二分的一道板子题，没有特别多注意的地方。

代码：

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int A, B, C, m, hp[maxn];
int D[maxn];
int calc(int x, int y, int z){
    if(x > A || y > B || z > C)    return 0;
    return ((x - 1) * B + (y - 1)) * C + (z - 1) + 1;
}
struct At{
    int ht;
    int lat, rat, lbt, rbt, lct, rct;
} attack[maxn];
bool check(int now){
    memset(D, 0, sizeof(D));
    for(int i = 1; i <= now; i++)
    {
        int dhp = attack[i].ht;
        int nx1 = attack[i].lat, ny1 = attack[i].lbt, nz1 = attack[i].lct;
        int nx2 = attack[i].rat, ny2 = attack[i].rbt, nz2 = attack[i].rct;
        D[calc(nx1, ny1, nz1)] += dhp;
        D[calc(nx1, ny1, nz2 + 1)] -= dhp;
        D[calc(nx2 + 1, ny1, nz1)] -= dhp;
        D[calc(nx1, ny2 + 1, nz1)] -= dhp;
        D[calc(nx2 + 1, ny1, nz2 + 1)] += dhp;
        D[calc(nx1, ny2 + 1, nz2 + 1)] += dhp;
        D[calc(nx2 + 1, ny2 + 1, nz1)] += dhp;
        D[calc(nx2 + 1, ny2 + 1, nz2 + 1)] -= dhp;
    }
    for(int i = 1; i <= A; i++)
        for(int j = 1; j <= B; j++)
            for(int k = 1; k <= C - 1; k++)
                D[calc(i, j, k + 1)] += D[calc(i, j, k)];
    for(int i = 1; i <= A; i++)
        for(int j = 1; j <= B - 1; j++)
            for(int k = 1; k <= C; k++)
                D[calc(i, j + 1, k)] += D[calc(i, j, k)];
    for(int i = 1; i <= A - 1; i++)
        for(int j = 1; j <= B; j++)
            for(int k = 1; k <= C; k++)
                D[calc(i + 1, j, k)] += D[calc(i, j, k)];
    for(int i = 1; i <= A * B * C; i++)
        if(D[i] > hp[i])    return true;
    return false;
}
int main(void)
{
    scanf("%d %d %d %d", &A, &B, &C, &m);
    for(int i = 1; i <= A * B * C; i++)    scanf("%d", &hp[i]);
    for(int i = 1; i <= m; i++)
        scanf("%d %d %d %d %d %d %d", &attack[i].lat, &attack[i].rat, &attack[i].lbt, &attack[i].rbt, &attack[i].lct, &attack[i].rct, &attack[i].ht);
    int L = 1, R = m, ans = 1;
    while(L <= R)
    {
        int mid = (L + R) / 2;
        check(mid) ? ans = mid, R = mid - 1 : L = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}

全球变暖

搜索题。

我看了网上的做法，其实蛮简单的，按照我的写法反而复杂了。

我首先对岛屿进行了染色，一座岛的颜色为一种。其次，对每座岛不会被淹没的地方做了标记。最后，遍历所有位置，如果一个位置是【陆地】，且【标记为不会被淹没】，以及【这块陆地的颜色没有在之前的遍历中出现过】，就使答案数$+1$.

代码：

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int n, vis[maxn][maxn];
int c, color[maxn][maxn];
int used[maxn * maxn], ans;

char board[maxn][maxn];

char get_read(){
    char ch = getchar();
    while(ch != '.' && ch != '#')    ch = getchar();
    return ch;
}

int fx[] = {0, 1, -1, 0, 0};
int fy[] = {0, 0, 0, 1, -1};

void dfs(int x, int y, int c){
    color[x][y] = c;
    for(int i = 1; i <= 4; i++)
        if(board[x + fx[i]][y + fy[i]] == '#' && !color[x + fx[i]][y + fy[i]])
            dfs(x + fx[i], y + fy[i], c);
}

int main(void)
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            board[i][j] = get_read();

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(!color[i][j] && board[i][j] == '#')    dfs(i, j, ++c);
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(board[i + 1][j] == '#' && board[i - 1][j] == '#' && 
               board[i][j + 1] == '#' && board[i][j - 1] == '#'  )    vis[i][j] = 1;
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(board[i][j] == '#' && !used[color[i][j]] && vis[i][j])   used[color[i][j]] = 1, ans++;
    
    printf("%d\n", c - ans);
    return 0;
}

这道题其实并不需要这么麻烦，只需要在每次遇到未曾访问的陆地时进行$DFS$，然后判断这块岛上面是否有出现不会沉没的陆地即可。

这里我搬运罗老师的代码：

#include<bits/stdc++.h>
using namespace std;

int n;
char a[1010][1010]; //地图
int vis[1010][1010]={0};  //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag;  //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
    vis[x][y] = 1;      //标记这个'#'被搜过。注意为什么可以放在这里
    if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')
        flag = 1;       //上下左右都是陆地，不会淹没
    for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
        int nx = x + d[i][0], ny = y + d[i][1];
      //if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0 && a[nx][ny]=='#') //题目说边上都是水，所以不用这么写了
        if(vis[nx][ny]==0 && a[nx][ny]=='#') //继续DFS未搜过的陆地，目的是标记它们
            dfs(nx,ny);
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
    int ans = 0 ;
    for(int i = 1; i <= n; i++)  //DFS所有像素点
        for(int j = 1; j <= n; j++)
            if(a[i][j]=='#' && vis[i][j]==0){
                flag = 0;
                dfs(i,j);
                if(flag == 0)  //这个岛全部被淹
                    ans++;     //统计岛的数量
            }
    cout<<ans<<endl;
    return 0;
}

这个写法还是比较整洁的（至少比我的好）。

然后这道题在我写的时候读错题了，是输出完全沉没的岛屿数量，而不是还未完全沉没的岛屿数量。几乎整题白给（我也不知道为啥还能过一个点…）。

下次一定注意！下次一定注意！下次一定注意！`(>﹏<)′

倍数问题

一道数论题。

写了两个部分分，$30$和$60$的。

现在回头看一下，写了$60$分的优化其实就离满分不远了欸，不过时间还是太紧凑了…

首先最容易想到的就是直接枚举，这样可以拿到$30$分。

代码：

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, r, maxx, a[maxn];
int main(void)
{
    scanf("%d %d", &n, &r);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            for(int k = j + 1; k <= n; k++)
            {
                if((a[i] + a[j] + a[k]) % r == 0)
                {
                    maxx = max(maxx, a[i] + a[j] + a[k]);
                }
            }   
    printf("%d\n", maxx);
    return 0;
}

这份暴力代码写完之后就可以开始着手优化了，因为可以通过对拍来保证正确性。

我们观察数据范围，考虑优化到$O(n^2)$。

如果需要$O(n^2)$，那么只能够枚举两个变量，考虑优化掉第三重循环。

题目给出的是三个数相加的和，这里我考虑到使用余数进行优化，因为确定了两个数之后就可以推导第三个数的余数。

然后，我需要使第三个数足够大。

因此，我将每一个数都存入其余数对应的桶里，再对每个桶的元素进行排序，保证我能取到的元素一定是最大的。

最后，按照这个流程寻找最大值即可。

为了保证正确性，编写对拍程序：

maker.cpp

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    srand(time(NULL));
    freopen("data.in", "w", stdout);
    int n = rand() % 100 + 1, k = rand() % 100 + 1;
    printf("%d %d\n", n, k);
    for(int i = 1; i <= n; i++)
        printf(i == n ? "%d\n" : "%d ", rand() % 100 + 1);
    return 0; 
}

fcc.cpp

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    srand(time(NULL));
    int cases = 1;
    do{
        printf("Case #%d:\n", cases++);
        system("maker.exe");
        system("my.exe < data.in > my.out");
        system("std.exe < data.in > std.out");
    }while(!system("fc my.out std.out"));
    printf("Fail!\n");
    system("pause");
}

对拍了$250$多组，没有发现错误，因此正确性得到一定保证。

代码：

#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int n, r, maxx, a[maxn];
vector<int> bl[maxn];
signed main(void)
{
    scanf("%lld %lld", &n, &r);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        bl[a[i] % r].push_back(a[i]);
    }
    for(int i = 0; i <= r - 1; i++)    sort(bl[i].begin(), bl[i].end());
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            int need = (r - (((a[i] % r) + (a[j] % r)) % r)) % r;
            int flag1 = a[i], flag2 = a[j];
            //最多会执行三次
            for(int k = bl[need].size() - 1; k >= 0; k--)
            {
                if(bl[need][k] == flag1)        flag1 = -1;
                else if(bl[need][k] == flag2)   flag2 = -1;
                else
                {
                    maxx = max(maxx, bl[need][k] + a[i] + a[j]);
                    break;
                }
            }
        }
    }
    printf("%lld\n", maxx);
    return 0;
}

其实到了这一步已经离胜利不远了。

我们只需要将前两重循环，从枚举$a[i],a[j]$换成枚举余数，就可以把$O(n^2)$优化到$O(k^2)$。

可惜考试时没想到这一步，也算是白给了…

代码：

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, k, maxx, a[maxn];
vector<int> v1[maxn];
int main(void)
{
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        v1[a[i] % k].push_back(a[i]);
    }
    for(int i = 0; i <= k - 1; i++)    sort(v1[i].begin(), v1[i].end());
    for(int i = 0; i <= k - 1; i++)
    {
        for(int j = 0; j <= k - 1; j++)
        {
            int r = ((k - i - j) + k) % k;
            int flag1, flag2, pos1, pos2;
            
            pos1 = v1[i].size(); pos2 = v1[j].size();
            
            if(i == j && v1[i].size() >= 2)
                flag1 = v1[i][pos1 - 1], flag2 = v1[j][pos2 - 2];
            else if(v1[i].size() && v1[j].size())
                flag1 = v1[i][pos1 - 1], flag2 = v1[j][pos2 - 1];
            else
                continue;
                
            int r1 = flag1, r2 = flag2;
            
            for(int l = v1[r].size() - 1; l >= 0; l--)
            {
                if(v1[r][l] == flag1)       flag1 = -1;
                else if(v1[r][l] == flag2)  flag2 = -1;
                else
                {
                    maxx = max(maxx, v1[r][l] + r1 + r2);
                    break;
                }               
            }
        }
    }
    printf("%d\n", maxx);
    return 0;
}

付账问题

嗯时间分配有点问题，写到这里差不多就剩十几分钟了，于是考试时就写了$10$分部分分。

~~（没错我只写对了标准差为0.0000的情况）~~

本来想写$30$分骗分的结果写挂了…

后面回过头来看一下，充其量是$Codeforces \ Div2 \ B \ or \ C$难度。

为了使得标准差最小，需要使得穷的人给尽可能多的钱，使得富人给尽可能少的钱，只有这样给的钱才会尽可能接近。

于是，够不到平均值的穷人，需要给完自己全部的钱。给钱后，重新计算剩下需要支付的钱，再求平均值。

以此类推，就能解决该题。

代码：

#include <bits/stdc++.h>
#define maxn 500005
#define int long long
using namespace std;
int n, S, a[maxn];
signed main(void)
{
    scanf("%lld %lld", &n, &S);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    double r = S, sum = 0;
    for(int i = 1; i <= n; i++)
    {
        if(a[i] < r / (n - i + 1))
        {
            sum += (a[i] - 1.0 * S / n) * (a[i] - 1.0 * S / n);
            r -= a[i];
        }
        else
        {
            sum += (n - i + 1) * (r / (n - i + 1) - 1.0 * S / n) * (r / (n - i + 1) - 1.0 * S / n);
            break;
        } 
    }
    printf("%.4lf", sqrt(sum / n));
    return 0;
}

小结

第二轮的蓝桥刷下来了。

虽然这次看起来都不难，但是我也确确实实没拿到高分。

真是难顶…

审题要审好，对拍要写对，时间分配要合理，$balabala$…

下一把就是$2019A$复盘了，希望一切顺利！

快快复完这些，还要去刷其他题呢…

还要打数理基础呢…

哇…