Codeforces Round #622 (Div. 2)

Codeforces Round #622 (Div. 2)

题目	难题	方法
A	简单	贪心
B	简单	贪心
C1	一般	枚举
C2	还行	线段树优化+枚举

---

A. Fast Food Restaurant

题意：

给你 a, b, c三种商品的个数， 问每个人只能最多买一种商品一个， 问最多可以卖出多次种组合。

题解：

A: 这题最多只有7种组合， 所有就贪心枚举这7种组合。

B：是的。

代码：

    #include<bits/stdc++.h>
    using namespace std;
     
    int main(){
        int a, b, c, t;
        scanf("%d", &t);
        while(t--){
            scanf("%d %d %d", &a, &b, &c);
            int cnt = 0;
             if(a){
                cnt++;
                a--;
            }
            if(b){
                cnt++;
                b--;
            }
            if(c){
                cnt++;
                c--;
            }
            vector<int>v;
            v.push_back(a);
            v.push_back(b);
            v.push_back(c);
            sort(v.begin(), v.end());
     
            if(v[2] && v[0]){
                cnt++;
                v[2]--, v[0]--;
            }
            if(v[2] && v[1]){
                cnt++;
                v[2]--, v[1]--;
            }
            if(v[1] && v[0]){
                cnt++;
                v[0]--, v[1]--;
            }
            
            if(v[0] && v[1] && v[2]){
                cnt++;
            }
            
           
            printf("%d
", cnt);
        }
    }

---

B. Different Rules

题意：

有n个人， 有两次比赛， 每场比赛会得到x分， 且每个人得到分都不一样， 且得到的分数范围在[1, n]

问小明在第一场得分位x, 第二场得分为y， 总分就是x+y最坏的情况排多少名， 最好的情况排多少名。

题解：

A：这题之间算出总分，最优的就是拿总分减去 n， 最差就是拿总分减去 1.

B：是的，然后得到的答案与 n去个min。

代码:

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

int main(){
    int t, n, x, y;
    scanf("%d", &t);
    while(t--){
        scanf("%d %d %d",&n, &x, &y);
        int z = x + y;
        z -= n;
        if(z <= 0) z = 1;
        else z++;
        printf("%d ", min(z, n));
        z = x + y;
        z = z - 1;
        printf("%d
", min(z, n));

    }
}

---

C1. Skyscrapers (easy version)

题意：

某城市要建n个楼， 每个楼的高度不超过，a[i]， 且某个楼， 左边和有便不能有比它高的。

题解：

A: 这题数据也就1000

B：是的， 所以我们直接枚举 以a[i]作为最高点 可以得到的最佳值

c：然后从枚举的点中取一个最大的， 至于为啥这样就对了， 自己好好想一下， 就可以相同了。

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

const int N = 1007;

int a[N], n;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    vector<int>ans;
    int pos = 0;
    long long maxn = 0;
    for(int i = 1; i <= n; i++){
        vector<int> v;
        int cnt = a[i];
        for(int j = i - 1; j; j--){
    
            if(cnt >= a[j]){
                v.push_back(a[j]);
                cnt = a[j];
            }else{
                v.push_back(cnt);
                //cnt = a[j + 1];
            }
        }
        reverse(v.begin(), v.end());
        v.push_back(a[i]);
        cnt = a[i];
        for(int j = i + 1; j <= n; j++){
            if(cnt >= a[j]){
                v.push_back(a[j]);
                cnt = a[j];
            }else{
                v.push_back(cnt);
        
            }
        }
        long long sum = 0;
        for(int j: v){
            sum += 1ll * j;
        }
        if(sum > maxn){
   
            maxn = sum;
            ans.clear();
            for(int j: v){
                ans.push_back(j);
            }
        }

    }

    for(int i: ans){
        printf("%d ", i);
    }
    puts("");
}

---

C2. Skyscrapers (hard version)

题意：

和上面的一样，只是数据为500000

题解：

A: 这题咋写？

B：上面我们用暴力求出以当前位置， 取最高求出，答案需要0（n）的时间。那么我就从这里开始优化。

A： 如何优化呢？

B: 用线段树， 你自己模拟一下， 你会发现这个区间修改操作， 所以用线段树可以操作。

A：好的我去试试。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 7;
int n;
ll a[N];
ll lsum[N], rsum[N];

vector<ll>v;

struct segment{
    ll sum, maxn;
}tree[4 * N];
#define m (l + r) / 2
#define lson 2  * node
#define rson 2 * node + 1

ll add[4 * N];

void push_up(int node){
    tree[node].sum = tree[lson].sum + tree[rson].sum;
    tree[node].maxn = max(tree[lson].maxn, tree[rson].maxn);
}

void push_down(int node, int nl, int nr){
    if(add[node]){
        tree[lson].sum = nl * add[node];
        tree[rson].sum = nr * add[node];
        tree[lson].maxn = add[node];
        tree[rson].maxn = add[node];
        add[lson] = add[node];
        add[rson] = add[node];
        add[node] = 0;
    }
}

void update(ll v, int pos, int l, int r, int node){
    if(l == r){
        tree[node].maxn = v;
        tree[node].sum = v;
        return;
    }
    push_down(node, m - l + 1, r - m);
    if(pos <= m) update(v, pos, l, m, lson);
    else update(v, pos, m + 1, r, rson);
    push_up(node);
}

void update(ll v, int ql, int qr, int l, int r , int node){
    if(ql <= l && qr >= r){
        tree[node].sum = v * (r - l + 1);
        tree[node].maxn = v;
        add[node] = v;
        return;
    }
    push_down(node, m - l + 1, r - m);
    if(ql <= m) update(v, ql, qr, l, m, lson);
    if(qr > m) update(v, ql, qr, m + 1, r, rson);
    push_up(node);
}

int query(ll v, int l, int r, int node){
    if(l == r)return l;
    push_down(node, m - l + 1, r - m);
    if(tree[lson].maxn >= v) return query(v, l, m, lson);
    return query(v, m + 1, r, rson);
}

int query1(ll v, int l, int r, int node){
    if(l == r)return l;
    push_down(node, m - l + 1, r - m);
    if(tree[rson].maxn >= v) return query1(v, m + 1, r, rson);
    return query1(v, l, m, lson);
}




int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }

    for(int i = 1; i <= n; i++){
        if(a[i] >= tree[1].maxn){
            update(a[i], i, 1, n, 1);
            lsum[i] = tree[1].sum;
        }else{
            int pos = query(a[i], 1, n, 1);
            update(a[i], pos, i, 1, n, 1);
            lsum[i] = tree[1].sum;
        }
    }

    for(int i = 1; i <= n; i++) update(0, i, 1, n, 1);
    for(int i = n; i; i--){
        if(a[i] >= tree[1].maxn){
            update(a[i], i, 1, n, 1);
            rsum[i] = tree[1].sum;
        }else{
            int pos = query1(a[i], 1, n, 1);
            update(a[i], i, pos, 1, n, 1);
            rsum[i] = tree[1].sum;
        }
    }
    int pos = 0;
    ll maxn = 0;
    for(int i = 1; i <= n; i++){
        ll cnt = lsum[i] + rsum[i] - a[i];
        if(cnt > maxn){
            maxn = cnt;
            pos = i;
        }
    }

    int i = pos;
    ll cnt = a[i];
    for(int j = i - 1; j; j--){
        if(cnt >= a[j]){
            v.push_back(a[j]);
            cnt = a[j];
        }else{
            v.push_back(cnt);
        }
    }
    reverse(v.begin(), v.end());
    v.push_back(a[i]);
    cnt = a[i];
    for(int j = i + 1; j <= n; j++){
        if(cnt >= a[j]){
            v.push_back(a[j]);
            cnt = a[j];
        }else{
            v.push_back(cnt);
        }
    }
    for(ll j: v){
        printf("%lld ", j);
    }
    puts("");

}