Codeforces Round #378 (Div. 2) C. Epidemic in Monstropolis 贪心+构造

Source

Codeforces Round #378 (Div. 2)

My Solution

题意：n个数构成的序列a，大的数可以合并掉小的数从而总数减1，然后给出一个由k个数构成的新序列b，问能否通过a中·部分大数逐步合并相邻相对较小的数 而得到b

贪心+构造

对于每一个bi，从a[ l ] 向右扫， 找出一个区间 sum{a[l.....r]} == bi,(l < r)     //没有出现==，而直接出现了 > bi，则直接ans = false; break;

然后这个区间 a[l......r] 就会大的数合并相邻的小的数，最终得到bi      //贪心策略是找到该期间最大的可以合并相邻数的数，合并以后比如是独有的最大数

//然后开始向右合并这个时候都是 maxi 'R'，即序号不变，然后到r后，向做合并直到 l。

这样跑一边，如果最终ans还是true则“YES”,否则“NO”

其中用一个queue<int, char> 来保存答案，最后再同意输出数据

此外

1、对于每个 a[l......r] (l < r)如果每个数都相等，则 ans = false;

比如

6

1 1 1 1 1 1

1

6

No

2、如果sum{bi} != sum{ai}，则ans = false;      //这个数据虐坑啊，习惯性思维是 sum{bi} 必定等于 sum{ai}，但毕竟这里没有说明 sum{bi} 必定等于 sum{ai}，所以要考虑不相等的情况

5

1 2 3 4 5

1

10

NO

复杂度 O(n^2)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, char> ic;
const int maxn = 1e6 + 8;

int a[maxn], b[maxn];
queue que;

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n, k, suma = 0, sumb = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){ cin >> a[i];
        suma += a[i];
    }
    cin >> k;
    for(int i = 1; i <= k; i++){ cin >> b[i];
        sumb += b[i];
    }


    int i, j = 1, sum = 0, maxv = 0, maxi = -1, sz = n, l = 1, r;
    bool ans = true;
    if(suma != sumb) ans = false;
    for(i = 1; i <= k; i++){ //cin >> b[i];
        sum = 0;
        maxv = 0;
        maxi = -1;
        if(a[l] == b[i]){l++; continue; }
        for(j = l; j <= sz; j++){
            sum += a[j];
            if(sum == b[i]){
                r = j;
                for(int x = l; x <= r; x++){
                    maxv = max(maxv, a[x]);
                }
                for(int x = l; x <= r; x++){
                    if(maxv == a[x]){
                        if(x == l){
                            if(a[x + 1] != maxv){
                                que.push(ic(x, 'R'));
                                maxi = x;
                                x++;
                            }
                        }
                        else if(x == r){
                            if(a[x - 1] != maxv){
                                que.push(ic(x, 'L'));
                                maxi = x-1;
                            }
                        }
                        else{
                            if(a[x + 1] != maxv){
                                que.push(ic(x, 'R'));
                                maxi = x;
                                x++;
                            }
                            else{
                                if(a[x - 1] != maxv){
                                    que.push(ic(x, 'L'));
                                    maxi = x-1;
                                }
                            }
                        }
//cout << que.back().first << " " << que.back().second << endl;

                        if(maxi != -1){
                            x++;
                            //cout << maxi << endl;
                            for(; x <= r; x++){
                                que.push(ic(maxi, 'R'));
                                //cout << x << " " << maxi << " " << "R" << endl; } for(x = maxi; x > l; x--){
                                que.push(ic(x, 'L'));
                            }
                            a[l] = sum;
                            for(int y = l+1; y + (r - l) <= sz; y++){ a[y] = a[y + (r - l)]; } sz -= (r - l); l++; break; } } } if(maxi == -1) ans = false; break; } else if(sum > b[i]){

                break;
            }

        }
        if(sum > b[i]){
            ans = false;
            break;
        }
        if(!ans) break;
    }


    if(ans){
        cout << "YES" << endl;
        while(!que.empty()){
            cout << que.front().first << " " << que.front().second << endl;
            que.pop();
        }
    }
    else cout << "NO" << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx