细节(水)题codeforce#378C

时间:2022-09-12 11:04:22

题目

网址

http://codeforces.com/contest/733/problem/C

大概题意

给你N个数,然后再给你经过合并操作后的K个数,求中间合并操作?

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <string>
#include <set>
#include <cmath>
#include <map>
#include <queue>
#include <sstream>
#include <vector>
#include <iomanip>
#define m0(a) memset(a,0,sizeof(a))
#define mm(a) memset(a,0x3f,sizeof(a))
#define m_1(a) memset(a,-1,sizeof(a))
#define f(i,a,b) for(i = a;i<=b;i++)
#define fi(i,a,b) for(i = a;i>=b;i--)
#define lowbit(a) ((a)&(-a))
#define FFR freopen("data.in","r",stdin)
#define FFW freopen("data.out","w",stdout)
#define INF 0x3f3f3f3f
#define DEBUG printf
typedef long long ll;
typedef long double ld;

const ld PI = acos(-1.0);

using namespace std;
#define SIZE 550

int a[SIZE];
int b[SIZE];

struct Chuan{
    int c_start;
    int c_end;
    int c_max;
};
struct Print{
    int num;
    char dire;
};
vector<Chuan> chuan;
queue<Print> print;
int main()
{
    int n,k;
    scanf("%d",&n);
    int i;
    f(i,1,n){
        scanf("%d",&a[i]);
    }
    scanf("%d",&k);
    int site=1;
    bool flag=0;
    f(i,1,k){
        scanf("%d",&b[i]);
        if(flag)continue;
        ll all=0;
        Chuan onechuan;
        onechuan.c_start=site;
        onechuan.c_max=0;
        int max_ele=0;
        while(all<b[i]){
            if(a[site]>max_ele){
                max_ele=a[site];
                onechuan.c_max=site;
            }
            else if(a[site]==max_ele){
                if(site-1>=onechuan.c_start&&a[site]>a[site-1]){
                    onechuan.c_max=site;
                }
                else if(site+1<=n&&all+a[site]+a[site+1]<=b[i]&&a[site]>a[site+1]){
                    onechuan.c_max=site;
                }
            }
            all+=a[site++];
        }
        onechuan.c_end=site-1;
        if(all!=b[i])flag=1;
        chuan.push_back(onechuan);
        //DEBUG("%d %d %d \n",onechuan.c_start,onechuan.c_max,onechuan.c_end);
    }
    if(flag){
        printf("NO\n");
        return 0;
    }
    if(site!=n+1){
        printf("NO\n");
        return 0;
    }
    i=0;
    while(!print.empty()){
        print.pop();
    }
    for(vector<Chuan>::iterator it=chuan.begin();it<chuan.end();it++){
        i++;
        if(it->c_start==it->c_end)continue;
        int pointer=it->c_max;
        if(pointer-1>=it->c_start&&a[pointer]>a[pointer-1]){
            while(pointer>it->c_start){
                Print oneprint;
                oneprint.num=i+pointer-it->c_start;
                pointer--;
                oneprint.dire='L';
                print.push(oneprint);
            }
            pointer=it->c_max;
            while(pointer<it->c_end){
                Print oneprint;
                oneprint.num=i;
                pointer++;
                oneprint.dire='R';
                print.push(oneprint);
            }

        }
        else if(pointer+1<=it->c_end&&a[pointer]>a[pointer+1]){
            while(pointer<it->c_end){
                Print oneprint;
                oneprint.num=i+it->c_max-it->c_start;
                //DEBUG("hello world!\n");
                pointer++;
                oneprint.dire='R';
                print.push(oneprint);
            }
            pointer=it->c_max;
            while(pointer>it->c_start){
                Print oneprint;
                oneprint.num=i+pointer-it->c_start;
                pointer--;
                oneprint.dire='L';
                print.push(oneprint);
            }
        }
        else {
            printf("NO\n");
            while(!print.empty()){
                print.pop();
            }
            return 0;
        }
        //DEBUG("%d %d %d\n",it->c_start,it->c_max,it->c_end);
    }
    puts("YES");
    while(!print.empty()){
        Print oneprint=print.front();
        print.pop();
        printf("%d %c\n",oneprint.num,oneprint.dire);
    }
    return 0;
}

经验教训

  1. 你离AC还差N个细节!
  2. 其实还是心不够静,思维跟不上,静下来后,你的智商会变高!
  3. 仔细阅读题意,然后注意关掉DEBUG!