Codeforces Round#622 div.2 回顾

题解

A - Fast Food Restaurant

题目地址：http://codeforces.com/problemset/problem/1313/A
外部链接：您可以选择洛谷来源或者vjudge来源的 Remote Judge。

还是比较简单的一个贪心题。根据题目描述的这个厨师的要求来看，他最多只能为七名客人上不同的菜：就是abc排列组合了。因为优先使用最多的菜式，所以排个序，再单独对七种情况if就可以了。

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t,a,b,c;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>c;
        int ans = 0;
        if(a>0)++ans,--a;
        if(b>0)++ans,--b;
        if(c>0)++ans,--c;  
        int ar[3] = {a,b,c};
        sort(ar,ar+3);
        if(ar[2]>0&&ar[1]>0)
        {
            --ar[2];
            --ar[1];
            ++ans;
        }
        if(ar[2]>0&&ar[0]>0)
        {
            --ar[2];
            --ar[0];
            ++ans;
        }
        if(ar[1]>0&&ar[0]>0)
        {
            --ar[1];
            --ar[0];
            ++ans;
        }
        a=ar[0];b=ar[1];c=ar[2];
        if(a>0&&b>0&&c>0)++ans;
        cout<<ans<<endl;
    }

    return 0;
}

最开始犹豫了好久应该怎么实现，，早知道最开始就一部排序贪心就好了，毕竟和abc没什么关系啊……嗒哈哈（）

B - Different Rules

题目地址：http://codeforces.com/problemset/problem/1313/B
外部链接：您可以选择洛谷来源或者vjudge来源的 Remote Judge。

这题目就很有意思：这就是真正的思维题吗？加了诸多的限制条件导致结论并不是那么的显而易见，倒也极大的增加了这个题目的难度（毕竟这题过的人数比C要少……~~不过也算不上是毒瘤题吧~~

首先是题目（啊我就翻译了这一个）：

题目描述
Nikolay最接近开始打算法竞赛了，且获得了一场著名比赛的决赛资格。这次决赛将会有包括Nikolay在内的n个参与者。向其他比赛一样，这场决赛由两轮组成。但是和之前不一样的是，组织者提出了新的规则：假设参赛者A第一轮排名x位，第二轮排名y位，那么参赛者A的总得分是x+y，总排名是总分小于等于A的总分的包括A在内的参赛者的数量。请注意：某些参赛者最后可能会有共同的总体排名。此外，在第一轮和第二轮的比赛中，没有多个参赛者并列的情况（也就是说，对于1~n之间的每个i，每轮比赛中都恰好只有一个人获得第i名）。
比赛结束后，Nikolay直到他在第一轮获得了第x位，第二轮获得了第y位的成绩。Nikolay不知道其他参赛者的成绩，但是他想知道在最坏和最好的情况下，他可以获得的总排名是多少。请帮助Nikolay解决这个问题。
输入格式
第一行包含一个整数t(1≤t≤100)，它是待解决的测试用例数；
在接下来的ttt行内，每行都包含三个整数n，x，y(1≤n ≤10⁹，1≤x，y≤n)，它们分别是这场决赛的参与者人数、Nikolay在第一轮和第二轮中取得的排名。
输出格式
每个测试样例输出两个整数：分别是Nikolay在在这次决赛中可以获得的最高排名和最低排名。
说明/提示
对于第一个测试样例的解释：
设这次比赛的 5 个参与者是 A-E。我们令 Nikolay 为参与者 A。那么对于 Nikolay 来说的最好的情况就是像下表所示的那样：
然而，这场比赛的结果也可能是这样：
在上述第一种情况，Nikolay 可以取得最高排名：第一位；然而在第二种情况中只能获得第三位。

说白了，比起最简单的最好最坏情况的限制条件就是：

没有并列情况的出现（其实降低了难度？）
总得分一致的情况下，玩家的排名尽可能的低

也就是说，最差的排名在尽可能多的人和他分数相等的时候取到：毕竟总分是有限的，相等的分能够压住玩家，就不要多浪费其他的小分数；最好的排名在尽可能多的人比他的分数大一的时候取到，这样也会尽可能不浪费分数来构造大分。

在纸上模拟或者脑内模拟，最终得到的结论就是：

x+y<=n时，最优情况是 1，最差情况是 min(x+y-1,n)。
x+y>n时，最优情况是 min(x+y-1,n)，最差情况是 n。

虽然模拟确实也能推导出式子，但是果然还是想要更加科学的解释啊：

最坏情况就是总得分等于x+y的人数：将一个整数k拆成两个整数的和的情况显然是k-1种。但是这个题目有限制：不能相等，要在参赛人数范围内。没事啊，这x+y-1只会比n大不会比n小，限制边界就行了啊（）

最好情况略微麻烦一点。刚才说了：如果我们希望某人排名比玩家低，那么最优做法就是让某人分数为x+y+1。进行一下分类讨论：

x+y不比n大：对于任何其他人，若第一轮p位，那么一定可能让他在第二轮排名为x+y+1-p甚至更差，所以此时玩家能得第一。
x+y比n大：这就比较的有意思。比玩家高的人是玩家的阻碍，但比玩家低的人可以成为玩家的助力，应当利用。若某人第一轮p位且比玩家最好水平要好，那么就让他第二轮继续p位，从而忽略他。这样做使得问题的规模缩小，且所有剩下的参赛人的排名绝对值变小（但不影响）——直到问题变成一个上面情况的子问题，玩家在剩下来的部分中得第一名：设已经忽略了t人，那么这样的问题规模缩减的边界是(x-t)+(y-t)=n-t，轻松解出t=x+y-n；剩下的部分中玩家第一，那么玩家名次是t+1=x+y-n+1。

呜呼……就是贪心啊，无他==

#include <iostream>
#include <algorithm>

using namespace std;

inline int best(int n, int x, int y)
{
    return min(max(x-n+y+1,1),n);
}

inline int worst(int n, int x, int y)
{
    return min(max(x+y-1,1),n);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t,n,x,y;
    cin>>t;
    while(t--)
    {
        cin>>n>>x>>y;
        cout<<best(n,x,y)<<' '<<worst(n,x,y)<<endl;
    }

    return 0;
}

ちくしょう……大家都说就算纸上推导也能画出来为啥我就是模拟不出来啊（）

哦，我知道了，可以在两场比赛中获得相同的排名，是我大意没有仔细看样例导致想复杂了，草。噫呜呜噫，我要回家（）

C1 - Skyscrapers (easy version)

题目地址：http://codeforces.com/problemset/problem/1313/C1
外部链接：您可以选择洛谷来源或者vjudge来源的 Remote Judge。

这题后面还有一个困难版本，难就难在n的取值范围变大了好多。这个版本n只有1e3，完全可以n方枚举。显然最终建成的大楼是山包形状的——最高点左侧单调不递减，右侧单调不递增，只是取不同的极大值可能会有不同的结果，找到最大的就好了。

因为数据范围太小的原因，甚至连极大值都不用找：只是枚举最高点然后向两侧走，更新答案就好了（）

代码就不贴了，C2再贴好了。

特别注意，别忘记开long long，这每一栋楼都是1e9，爆int轻而易举。

C2 - Skyscrapers (hard version)

题目地址：http://codeforces.com/problemset/problem/1313/C2
外部链接：您可以选择洛谷来源或者vjudge来源的 Remote Judge。

根据刚才的分析，这个楼最终盖起来的样子一定是中间有一个峰值，然后两侧的高度分别是方向相反发不严格的两个单调序列。根据刚才说的暴力方法，向两侧行走的时候直到遇到比当前楼层高度低的楼层之后，再更新楼层高度。也就是说，假设第 $i$ 个楼是中心的“峰值”，高度为 $h_i$ ；先考虑它的左侧 $ k<i $ 是左侧第一个高度低于它的楼；另设 $f_i$ 是 $i$ 左侧的楼层的高度和的最大值，那么可以得到这样的推导式：

$f_i = f_k + h_k + h_i \cdot (i-k-1)$

相应的，对于中心楼层 $i$ 右侧的第一个小于 $i$ 的楼 $k>i$ ，令 $f'_i$ 是 $i$ 右侧的楼层的高度和的最大值，也可以得到类似的关系：

$f'_i = f'_k + h_k + h_i \cdot (k-i-1)$

知道了这个表达式之后，我们就能用比C1中的暴力要快得多的方法求出以i作为峰值时的最高高度总和。那么问题就转化成了我们应该怎么样快速地求出序列中i两侧的第一个小于它的高度的楼层。好在这个问题可以使用一个经典的数据结构单调栈来解决。我们先简单的看一下单调栈的定义：

单调栈：
顾名思义，单调栈中存放的数据是单调有序的；根据这个次序调栈也分为单调递增栈和单调递减栈
单调递增栈：数据出栈的序列为单调递增序列
单调递减栈：数据出栈的序列为单调递减序列
特别注意：这里所说的递增递减指的是出栈的顺序，而不是在栈中数据的顺序。
那么，为了维持这个有序性，在push和pop的时候就要检查栈顶元素。根据检查结果还可以方便的构造两个数组 L 和 R，分别储存了当前元素 i 两侧的第一个小于/大于（等于）的元素的序号。这个行为的时间复杂度是 O(n) 的，因为序列中的每一个元素只会入栈一次。
数组 L 和 R 的具体含义取决于检查栈顶元素使用的运算符：例如，如果你使用>作为判定，那么 L 数组就是第一个小于等于 i 的元素，而 R 数组是第一个小于 i 的元素。应该注意到两个数组的严格单调性不一致。

那么问题就变得简单了起来，我们只需要使用 O(n) 的时间使用单调栈构建出序列的 L 和 R 数组，再根据这两个数组以及上面推出的递推公式完成对每一个位置作为峰值的最好结果的求解，进行比较筛选就能找到最大的值了。再根据最大值出现的位置填写每栋楼的高度输出即可。

此外，这个题目还有一种使用线段树和分治思想的方法，下次写好了也会在这里补上的。下面是使用单调栈完成的代码：

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;
typedef long long longs;

const int N = 5e5+50;
longs n,m[N];               
longs ans[N];               
int l[N],r[N];
longs fl[N],fr[N];
stack<int> s;

inline void pop(int i)
{
    r[s.top()] = i;
    s.pop();
}

inline void push(int i)
{
    while(!s.empty()&&m[s.top()]>m[i]) pop(i);
    if(s.empty()) l[i] = 0;
    else l[i] = s.top();
    s.push(i);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;
    const int npos = n+1;
    fl[0] = fl[npos] = 0;
    fr[0] = fr[npos] = 0;
    m[0] = m[npos] = 0;

    for(int i=1;i<=n;++i)
    {
        cin>>m[i];
        push(i);
    }
    while(!s.empty()) pop(npos);

    for(int i=1,j=n;i<=n;++i,--j)       // 根据递推式计算
    {
        fl[i] = fl[l[i]]+m[i]*(i-l[i]-1)+m[l[i]];
        fr[j] = fr[r[j]]+m[j]*(r[j]-j-1)+m[r[j]];
    }
    longs max = 0, tmp; int pos = 0;
    for(int i=1;i<=n;++i)               // 加上m[i]进行比较
        if((tmp=fl[i]+fr[i]+m[i])>max)
            max = tmp, pos = i;
    ans[pos] = m[pos];                  // 填值
    for(int i=pos-1;i>0;--i)
        ans[i] = min(m[i],ans[i+1]);
    for(int i=pos+1;i<=n;++i)
        ans[i] = min(m[i],ans[i-1]);
    for(int i=1;i<=n;++i)
        cout<<ans[i]<<' ';
    return 0;
}