codeforces 733C Epidemic in Monstropolis 贪心

题意很简单，很明显看出最后形成的队列，可以把最初的队列划分成一段一段。也就是问题转化成了某一段能不能通过吞吃变成一个。

起初总是受到误导，认为一个队列中是同时开始吞吃的。实际上从开始到最后只有一个怪兽在吃。就是最大的那一个。只要一个队列中存在一个最大的，同时他们又不全部相同。那么这个队列就可以最后变成一个怪兽。

这道题真的是烦啊，总是写错。看来还是代码基本功不扎实。主要是更新队列中点的下标的时候总是有一些小错误。代码如下：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <fstream>
#include <istream>
#include <ostream>
#include <complex>
#include <cstring>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <new>
#include <set>
#include <map>

using namespace std;

typedef pair<int, char> pic;
typedef long long int LL;
const int INF = 0x3f3f3f3f;
const int maxn = 1000;
vector<pic> ans;
int n, a[maxn];

void add_ans(int s, int e, int cnt){
    int len = e - s + 1;
    int mmax = -1, m;
    for (int i = s; i <= e; i++){
        if (mmax<a[i]&&((i>=s+1&&a[i]>a[i-1])||(i<e&&a[i]>a[i+1]))){
            mmax = a[i];
            m = i;
        }
    }

   while (len > 1){
        if (m >= s + 1 && a[m] > a[m - 1]){//往左吃
            ans.push_back(pic(m - s + 1 + cnt, 'L'));
            a[m] += a[m - 1];
            for (int i = m; i <= e; i++) a[i - 1] = a[i];
            e--;
            m--;
        }

        else if (m < e && a[m] > a[m + 1]){//往右吃
            ans.push_back(pic(m - s + 1 + cnt, 'R'));
            a[m + 1] += a[m];
            for (int i = m + 1; i <= e; i++) a[i - 1] = a[i];
            e--;
        }

        len--;
    }
}

bool same(int s, int e){
    for (int i = s + 1; i <= e; i++)
        if (a[i] != a[i - 1])
            return false;
    return true;
}

int main()
{

    //freopen("1.txt", "r", stdin);
    scanf("%d", &n);
    LL sum = 0;
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    int k, b[maxn], ok = 1;
    LL sum1 = 0;
    scanf("%d", &k);
    for (int i = 1; i <= k; i++){
        scanf("%d", &b[i]);
        sum1 += b[i];
    }
    if (sum1 != sum) ok = 0;

    int j = 0;
    for (int i = 1; i <= k; i++){
        LL sum2 = 0;
        int s = j + 1;
        for (j++; j <= n; j++){
            sum2 += a[j];
            if (sum2 >= b[i]) break;
        }
        if (sum2 > b[i]) {ok = 0; break;}

        if (s == j) continue;
        else if (!same(s, j)) add_ans(s, j, i - 1);
        else {ok = 0; break;}
    }

    if (!ok) printf("NOn");
    else{
        printf("YESn");
        for (pic P : ans)
            printf("%d %cn", P.first, P.second);
    }
    return 0;
}

最后

以上就是受伤冥王星为你收集整理的codeforces 733C Epidemic in Monstropolis 贪心的全部内容，希望文章能够帮你解决codeforces 733C Epidemic in Monstropolis 贪心所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。