CF-577-2

Codeforces Round #577 (Div. 2)

A.Important Exam

问学生分数总和最大为多少

那么就是每道题选的最多的选项为答案，计算即可

B.Zero Array

如果sum是奇数的一定不行

如果是偶数的话就看一下最大的值是不是比sum的一半小，是YES否NO

因为如果最大比一半还多，说明有一部分需要自己和自己配对

C.Maximum Median

保证奇数个数，很友好

比中位数小的我们就不用管了，因为没有价值

想要保持中位数不断增大就要保证中位数之后的数不小于中位数

所以说，中位数和ai之间的数不断增加到ai+1，直到M用完（看代码理解）

代码：（注意开LL）

LL T,N,M,K;
/*-------------------------------------------------------------------------------------------*/
vector<LL> a;
/* ------------------------------------------------------------------------------------------*/
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    cin >> N >> M;
    int x;
    for(int i = 0;i < N;i++)
    {
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(),a.end());
    int mid = N / 2;
    LL cnt = 1;
    for(int i = mid+1;i < N;i++)
    {
        LL n = cnt * (a[i] - a[mid]);
        if(n <= M)
        {
            a[mid] = a[i];
            cnt++;
            M -= n;
        }
        else
        {
            int k = M / cnt;
            a[mid] += k;
            M = 0;
            break;
        }
    }
    if(M)
    {
        int k = M / cnt;
        a[mid] += k;
        M = 0;
    }
    cout << a[mid] <<endl;
    return 0;
}

D.Treasure Hunting

题目思路：

我们可以发现，当我们吃完一层的宝藏的时候最后一定停留在最左边的宝藏，或者最右边的宝藏

所以就每次计算出到 i 层的最左和最右的宝藏的路劲进行dp

还可以发现，你去下一层的时候，选的安全列就是你现在位置的左右最近的安全列，这是最优的选择，走远也没有用

所以说，转移一次层数就会有有8条路可以选，枚举这八条路就可以了

L1 -> L2 , L1 -> R2 , R1 -> L2 , R1 -> R2,出发点你可选左或右的安全列，所以 * 2，就是8条

这个算出来的是 i -> i+1层的，然后你再加上1 -> i层的路径，比较找到从1层到达L2和R2的最短路

注意如果这一层没有宝箱就先空着，只算上了一层楼，不转移 L，R

注释很全，可以看注释

因为中间的逻辑错误，改了很久没有找到，令人心痛，不知道写的时候怎么想的，只考虑了当前路径最短，忘了加前面的比较

题目代码：

LL T,N,M,K;
/*-------------------------------------------------------------------------------------------*/
int Left[MAX];//最左边的宝藏
int Right[MAX];//最右边的宝藏
int lsafe[MAX];//当前列左边最近的出口
int rsafe[MAX];//当前列右边最近的出口
vector<int> b;//安全出口
/* ------------------------------------------------------------------------------------------*/
 
void lsize(int mid,LL *r, LL *l,int i)
{
    LL t1,t2;
    t1 = abs(mid - lsafe[mid])  + 1;
    t2 = abs(rsafe[mid] - mid)  + 1;
    *r =  min(abs(lsafe[mid] - Left[i] )  +  (Right[i] - Left[i]) + t1,abs(rsafe[mid] - Left[i] ) + (Right[i] - Left[i]) + t2);
    *l =  min(abs(lsafe[mid] - Right[i])  +  (Right[i] - Left[i]) + t1,abs(rsafe[mid] - Right[i]) + (Right[i] - Left[i]) + t2);
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    //2.选择左or右的宝藏
    //3.吃完一行的宝藏到达左or右
    //1.找到安全出口
    //现在吃完的宝藏步数最小
    int k,q;
    cin >> N >> M >> k >> q;
    int x,y;
    for(int i = 0;i < k;i++)//0代表没有宝藏
    {
        cin >> x >> y;
        if(Left[x] == 0)
        {
            Left[x] = Right[x] = y;
        }
        else
        {
            Left[x] = min(Left[x],y);
            Right[x] = max(Right[x],y);
        }
    }
    int temp;
    for(int i = 0;i < q;i++)
    {
        cin >> temp;
        b.push_back(temp);
    }
    sort(b.begin(),b.end());
    for(int i = 1;i <= M;i++)//INF没有安全
    {
        auto it = lower_bound(b.begin(),b.end(),i);
        if(it == b.end())
        {
            rsafe[i] = INF;
            it--;
            lsafe[i] = *it;
            continue;
        }
        if(it == b.begin())
        {
            if(*it == i) lsafe[i] = i;
            else lsafe[i] = -INF;
            rsafe[i] = *it;
            continue;
        }
        if(*it == i)
        {
            lsafe[i] = rsafe[i] = i;
        }
        else
        {
            rsafe[i] = *it;
            it--;
            lsafe[i] = *it;
        }
    }
    LL l,r;
    int L,R;
    if(Right[1])//第一层从1，1出发
    {
        l = Right[1] - 1 + Right[1] - Left[1];
        r = Right[1] - 1;
        R = Right[1];
        L = Left[1];
    }
    else
    {
        L = R = 1;
        l = r = 0;
    }
    LL cnt = 0;
    for(int i = 2;i <= N;i++)
    {
        if(!Right[i])
        {
            cnt++;
            continue;
        }
        LL ar,al;//到达下一层左右宝藏的最短路
        lsize(R,&ar,&al,i);//从上一层的右宝藏出发
        LL br,bl;//到达下一层左右宝藏的最短路
        lsize(L,&br,&bl,i);//从上一层的左宝藏出发
        LL tl,tr;
        tl = l + bl;/*第一次写错了，只比了比较从L1 -> L2 , R1 -> L2的最短路，没有加l，成了贪心了，wa*/
        tl = min(r + al,tl);//比较从1 -> L2 ,  1 -> L2的最小值 
        tr = l + br;
        tr = min(r + ar,tr);//比较从1 -> R2 ,  1 -> R2的最小值
        L = Left[i];//转移L，R
        R = Right[i];
        l = tl + cnt;//加上中间没有宝藏的层数
        r = tr + cnt;
        cnt = 0;
    }
    cout << min(r,l) <<endl;
    return 0;
}