Epidemic in Monstropolis

greedy

New sequence m The number must be determined by the continuity of the original sequence m It's made up of subsequences , Just find the largest number in each successive subsequence .

Attention should be paid to the details ： A continuous subsequence may have many maxima , One of the left and right numbers of the maximum number must be less than this number ; And subscript processing .

The code is as follows ：

 import sys
n = int(input())
a = [int(x) for x in input().split()]
m = int(input())
b = [int(x) for x in input().split()]
sum1,sum2 = 0,0
for i in a:
sum1 += i
for i in b:
sum2 += i
if sum1 != sum2:
print('NO')
sys.exit(0)
s = []
idx = 0
for i in range(m):
t = b[i]
oo = idx
mm = idx
while t > 0:
t -= a[idx]
if a[mm] < a[idx]:
mm = idx
idx += 1
if t < 0:
print('NO')
sys.exit(0)
if mm == oo:
while mm+1<idx and a[mm]==a[mm+1]:
mm = mm+1
flag = 0
if mm-1>=oo and a[mm]>a[mm-1]:
flag = 1
elif mm+1<idx and a[mm]>a[mm+1]:
flag = 2
elif idx-oo == 1:
continue
if flag == 0:
print('NO')
sys.exit(0)
elif flag == 1:
for x in range(mm,oo,-1):
s.append([x-oo+i,'L'])
for x in range(mm,idx-1):
s.append([i,'R'])
elif flag == 2:
for x in range(mm,idx-1):
s.append([mm-oo+i,'R'])
for x in range(mm,oo,-1):
s.append([x-oo+i,'L'])
print('YES')
for x in s:
print(x[0]+1,x[1])

Epidemic in Monstropolis More articles about

1. CF733C Epidemic in Monstropolis[ simulation structure greedy ]

C. Epidemic in Monstropolis time limit per test 1 second memory limit per test 256 megabytes input s ...

2. Codeforces Round #378 (Div. 2) C. Epidemic in Monstropolis simulation

C. Epidemic in Monstropolis time limit per test 1 second memory limit per test 256 megabytes input s ...

3. Codeforces Round #378 (Div. 2)-C. Epidemic in Monstropolis

C. Epidemic in Monstropolis time limit per test 1 second memory limit per test 256 megabytes input s ...

4. 【16.52%】【codeforces 733C】Epidemic in Monstropolis

time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard ou ...

5. codeforces733-C. Epidemic in Monstropolis Greedy and linked list

The question Now there's a monster sequence a[i], Monsters with large weights can eat monsters with small weights , After eating, the weight of the monster with large weight will become the sum of the two weights , Only neighboring monsters can eat After eating , Location merging , Queue forward , Renumber from left to right , Repeat the process , And then to ...

6. Codeforces 733C：Epidemic in Monstropolis（ Violence, greed ）

http://codeforces.com/problemset/problem/733/C The question : Give a sequence of monster volumes ai, Monsters can only eat neighboring monsters , And only monsters that are strictly larger than their neighbors can eat , After eating , ...

7. CodeForces 733C Epidemic in Monstropolis

simulation . A continuous period of $a$ Synthesis of a $b$. If the number in each paragraph is only $1$ individual , So you can synthesize . If the number of numbers is greater than or equal to $2$ individual , If it's all the same , So it's impossible to synthesize , Otherwise, find a maximum position that can be moved and start moving . I started with a ...

8. C. Epidemic in Monstropolis

http://codeforces.com/contest/733/problem/C A disgusting simulation problem . Notice that if you can make it b[1], that a The prefix and must have a satisfaction that b[1] Of , because , If you skip some ...

9. Codeforces Round #378 (Div. 2) A B C D In construction

A. Grasshopper And the String time limit per test 1 second memory limit per test 256 megabytes input ...

Random recommendation

1. afx , afxMessageBox , MessageBox

afx It starts with global functions , Can be used anywhere MessageBox yes CWnd Subfunction of , Only in CWnd Window class object with , AfxMessageBox Function prototype of int AfxMessageBox( LPC ...

2. turn ： sql server2008 Field type details

bit integer bit Data types are integers , Its value can only be 0.1 Or null . This data type is used to store data with only two possible values , Such as Yes or No.True or False .On or Off. Be careful : A data type that saves a lot of space , If you can ...

3. Java in ACM/ICPC

Catalog Java stay ACM/ICPC Features in stay ACM/ICPC Use in Java Something to be aware of Java And high precision calculation 1.Java stay ACM/ICPC Features in Java Grammar and C++ Almost the same Java In the execution plan ...

4. ng Form validation , Errors are not displayed until they are submitted

Display error messages only after submitting the form Sometimes I don't want to display an error message while the user is typing . The current error message will be displayed as soon as the user enters the form . because Angular Great data binding features , It can happen . Because everything can be done in a moment ...

5. Java Basic study notes 26 JDBC

What is? JDBC JDBC(Java DataBase Connectivity) Namely Java Database connection , To put it bluntly, it is to use Java Language to operate the database . It turns out that we operate the database in the console SQL Statement to operate on the database ,J ...

6. Python How to customize a timer in

import time as t class MyTimer(): # Initialize constructor def __init__(self): self.prompt = " The clock didn't start ..." s ...

7. dir function

dir function : dir() Is a built-in function , Used to list all the properties and methods of an object Let's try : Use the following two tests test2 Do experiments with documents # Create a class , Two constants , Function in class test1, Class , class ...

8. AtCoder WTF 2019 C2. Triangular Lamps Hard

Topic link I feel that this kind of question is really uncanny ,$$\text{OI}$$ It would be great if there were more such topics in the paper . The question : There is a two-dimensional trigonometric coordinate system , It's roughly as shown ( The picture is from atcoder It's stolen from the house ): Every... In the coordinate system ...