سروش در ابتدای صف ورود به سالن سینما، منتظر یکی از دوستانش است. دوست سروش در انتهای صف…
- User
سروش در ابتدای صف ورود به سالن سینما، منتظر یکی از دوستانش است. دوست سروش در انتهای صف ایستاده و به دنبال او میگردد. به جز سروش و دوست او، n n نفر دیگر در صف، بین آن دو، ایستادهاند که از ابتدای صف به ترتیب با شمارههای ۱ تا n n شمارهگذاری شدهاند.
با توجه به اینکه تمام این افراد صرفاً برای گذراندن وقت به سینما آمده بودند، تصمیم گرفتند به جای دیدن فیلم، کاری کنند که سروش و دوستش نتوانند یکدیگر را ببینند.
در هر لحظه تمامی افراد درون صف در یک جهت نگاه میکنند. جهت نگاه تمامی افراد در هر ثانیه یا به سمت سروش و ابتدای صف است و یا به سمت دوست او و انتهای صف. در هر ثانیه هر فرد اگر در راستایی که نگاه میکند، فرد دیگری که در حال حاضر از او اکیداً بلندتر باشد ببیند، قدش را به اندازهی یک سانتیمتر افزایش میدهد.
علی به مدت m m ثانیه این صحنه را نگاه میکند و به ازای هر یک از ثانیهها جهت نگاه افراد را یادداشت میکند. به عبارت دقیقتر او به ازای هر عملیات یک حرف انگلیسی یادداشت میکند که اگر برابر L باشد افراد در ثانیهی i i ام به سمت سروش و ابتدای صف نگاه میکنند و در صورتی که برابر R باشد، افراد در این ثانیه به سمت دوست سروش و انتهای صف نگاه میکنند.
او قد تمامی n n نفر را پیش از شروع عملیاتهای گفته شده، میداند. به عبارت دقیقتر، او میداند که قد نفر i i ام پیش از شروع عملیاتها h i h i سانتیمتر است. برنامهای بنویسید که با داشتن قد ابتدایی و جهت نگاه افراد در هر ثانیه، قد نهایی هر فرد را محاسبه کند.
ورودی در خط اول ورودی دو عدد طبیعی n n، تعداد افراد درون صف، و m m، تعداد ثانیههایی که علی عملیات گفته شده را مشاهده کرده، آمده است.
در خط دوم ورودی n n عدد h 1 , h 2 , … , h n h 1 ,h 2 ,…,h n آمده است که قد ابتدایی افراد را نشان میدهند.
در خط سوم ورودی یک رشتهی به طول m m از حروف R و L آمده است که حرف i iام این رشته، حرف نوشته شده در ثانیه i iام را نشان میدهد. 1 ≤ n , m ≤ 200
000 1≤n,m≤200 000 0 ≤ h i ≤ 1 0 9 0≤h i ≤10 9
خروجی در تنها خط خروجی n n عدد چاپ کنید که عدد i iام قد نهایی فرد i iام را نشان میدهد.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۰۰ بدون محدودیت اضافی مثال ورودی نمونه ۱ 5 2 1 3 1 3 1 RL Plain text خروجی نمونه ۱ 2 3 3 3 2 Plain text ورودی نمونه ۲ 5 4 5 4 3 2 1 LLRL Plain text خروجی نمونه ۲ 5 5 5 5 4 java
- Assistant
To tackle this problem efficiently, it's essential to recognize the dynamic nature of how each person’s height can be incremented based on the sequence of operations (
LorR). Here's a step-by-step approach to solving the problem:Step-by-Step Explanation:
-
Initialization:
- You are given
npeople in a line, each with an initial heighth[i]. - You have
moperations, each being eitherLorR.
- You are given
-
Understanding Operations:
L(Left): For eachLoperation, traverse the line from left to right. Maintain acurrent_maxto track the tallest person seen so far. For each person, ifcurrent_maxis greater than their current height, increment their height by 1. Updatecurrent_maxas necessary.R(Right): For eachRoperation, traverse the line from right to left. Similarly, maintain acurrent_maxto track the tallest person seen so far from the right. For each person, ifcurrent_maxis greater than their current height, increment their height by 1. Updatecurrent_maxas necessary.
-
Efficient Simulation:
- Given that both
nandmcould be as large as 200,000, a naive simulation with nested loops would lead to an impractical O(n*m) time complexity. - Instead, the solution involves iterating through each operation and performing the necessary updates in a single pass, ensuring that the total time complexity remains manageable.
- Given that both
-
Implementation:
- Use a loop to process each operation.
- Depending on whether the operation is
LorR, perform a single pass through the line to update heights as described. - After processing all operations, output the final heights of all individuals.
Java Implementation:
Below is the Java implementation of the described approach:
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Read first line: n and m String[] firstLine = br.readLine().split(" "); int n = Integer.parseInt(firstLine[0]); int m = Integer.parseInt(firstLine[1]); // Read heights String[] heightStr = br.readLine().split(" "); long[] h = new long[n]; for(int i=0;i<n;i++) { h[i] = Long.parseLong(heightStr[i]); } // Read operations String operations = br.readLine(); for(int opIdx=0; opIdx < m; opIdx++) { char op = operations.charAt(opIdx); if(op == 'L') { long current_max = Long.MIN_VALUE; for(int i=0;i<n;i++) { if(current_max > h[i]) { h[i] +=1; } if(h[i] > current_max) { current_max = h[i]; } } } else { // 'R' long current_max = Long.MIN_VALUE; for(int i=n-1;i>=0;i--){ if(current_max > h[i]) { h[i] +=1; } if(h[i] > current_max) { current_max = h[i]; } } } } // Build output StringBuilder sb = new StringBuilder(); for(int i=0;i<n;i++) { sb.append(h[i]).append(" "); } System.out.println(sb.toString().trim()); } }Explanation of the Code:
-
Reading Input:
- The first line contains
nandm. - The second line contains the initial heights of the
npeople. - The third line contains the sequence of
moperations (LorR).
- The first line contains
-
Processing Operations:
- Iterate through each operation:
- If the operation is
L, traverse from left to right, updating heights based on the current maximum height to the left. - If the operation is
R, traverse from right to left, updating heights based on the current maximum height to the right.
- If the operation is
- Iterate through each operation:
-
Output:
- After processing all operations, print the final heights of the people in line.
This approach ensures that each operation is processed in O(n) time, resulting in an overall time complexity of O(n*m). Given the large constraints, this implementation is efficient and should work within the time limits for the problem.
-