კრიმინალები მწკრივში



კრიმინალები დგანან ციხის კაფეტერიის რიგში, მათი რაოდენობაა n. თითოეულს აქვს გავლენა, რომელიც ფასდება ქულით 1-დან n-მდე. მათ მოსწყინდათ მოცდა და გადაწყვიტეს ერთმანეთი დაეხოცათ შემდეგი წესით: ყოველ წუთში თითოეული კრიმინალი კლავს მის მარჯვნივ მდგომ კრიმინალს, თუ საკუთარი გავლენა უფრო მაღალი ქულით ფასდება, ვიდრე მარჯვნივ მდგომის. ერთდროულად შესაძლებელია კრიმინალმა მოკლას და მოკვდეს კიდეც და ამავდროულად, ყველა კრიმინალის გავლენის ქულა უნიკალურია.
გეძლევა კრიმინალების განლაგების სია საწყისი მომენტისათვის, თითოეული კრიმინალისთვის შემოდის მისი გავლენის ქულა. დაითვალე, რამდენი წუთის შემდეგ დადგება წუთი, როდესაც ერთმანეთს აღარავინ მოკლავს.

შემოსატანი მონაცემები:
პირველ ხაზზე შემოდის კრიმინალების რაოდენობა n, (1 ≤ n ≤ 105).  მერე ხაზზე შემოდის 1-დან n-ის ჩათვლით, ჰარით (space-ით) გამოყოფილი რიცხვები, კრიმინალების გავლენის კოეფიციენტები მარცხნიდან მარჯვნივ.

გამოსატანი მონაცემები:
გამოიტანოთ ერთი რიცხვი, რომელიც შეესაბამება წუთების რაოდენობას, რომლის გასვლის შემდეგაც რიგში აღარავინ მოკვდება.

 

 

მაგალითი I:

შემოდის:

10

10 9 7 8 6 5 3 4 2 1

პასუხი:

2

მაგალითი II:

შემოდის:

6

1 2 3 4 5 6

პასუხი:

0


მაგალითის გარჩევა:
პირველ მაგალითში კრიმინალების რაოდენობა თითოეული წუთისთვის ასე გამოიყურება: [10 9 7 8 6 5 3 4 2 1]  →  [10 8 4]  →  [10]. მაშასადამე 2 წუთის შემდეგ აღარავინ კვდება.


 

ამოცანის ამოსახსნელად განვიხილოთ ორი მიდგომა.

პირველი:

ეს მიდგომა ყველაზე მარტივად და ლოგიკურადაა აგებული, შევინახოთ მონაცემები და უბრალოდ გავაკეთოთ სიმულაცია, გადავუყვეთ მონაცემებს საჭირო რაოდენობით და მოვნიშნოთ კრიმინალი მკვდარად თუ მოკვდა ამ ჯერზე, ყოველჯერზე შევამოწმოთ მოკვდა თუ არა ვინმე და წუთი როდესაც აღარავინ მოკვდება იქნება პასუხი. თუმცა, როდესაც მონაცემები 105 გვაქვს ეს მიდგომა არ გამოგვადგება, ზოგადი ალგორითმული სირთულე გამოდის O(t*n) სადაც t საბოლოო პასუხია, ხოლო n კრიმინალთა რაოდენობა. თეორიულად t-ს მაქსიმუმი n-მდე აღწევს, შესაბამისად, ყველაზე ცუდ შემთხვევაში სირთულე O(n2) გვაქვს, რაც ნამდვილად არაა ეფექტური მიდგომა.

 

მეორე:

ეს მიდგომა შედარებით რთული აღსაქმელია, თუმცა ბევრად სწრაფად მუშაობს. ამოხსნისათვის დაგვჭირდება სტეკის და წყვილის სტრუქტურები. წყვილებში შევინახოთ გავლენის ქულა პირველ ველში, მერამდენე წუთზე მოკვდა მეორე ველში და ჩავთვალოთ, რომ თუ მეორე ველი nზე მეტია უბრალოდ არ კვდება და ეს პასუხში არ შეგვაქვს. მიდგომა შემდეგია: ყველა ჯერზე i ური კრიმინალი კვდება, თუ მასზე წინ მდგომზე ნაკლები ქულა აქვს და მასზე წინ მდგომი არ მომკვდარა iურ წევრზე წინ. თუ iური წევრი არ კვდება i-1ურის მიერ, მაშინ iური მის წინ მდგოზე ერთი წუთით ან კიდევ უფრო გვიან მოკვდება. ამავდროულად, თითოეულ წუთზე, არ კვდება პირველი ვინც დგას, ან პირველი k კრიმინალი, თუ მათი ქულები ზრდადობითაა დალეგებული.

განვიხილოთ იმპლემეტაციის დეტალები, რათა ამოხსნა უფრო ცხადი გახდეს:

ფსევდო კოდი:

შევქმნათ ცარიელი წყვილების სტეკი;

შემოვაყვანინოთ N;

ციკლში დავტრიალდეთ N ჯერ:

შემოვაყვანინოთ ახლანდელი ქულა;

საწყისად მივიღოთ, რომ ეს კრიმინალი მენულე წუთზე მოკვდა;

თუ ამ კრიმინალამდე სტეკში მასზე დაბალი გავლენის კრიმინალები გვყავს ჩაყრილი მასზე წინ, ამოვყაროთ, ამას მაინც ვერ მოკლავენ და მათი სიკვდილის დროც უკვე დათვლილია. ამავდროულად, ახლანდელი კრიმინალი თითოეული ამოგდებულის შემდეგ წუთზე ან უფრომ გვიან კვდება, როგორც ზევით აღვნიშნეთ.

თუ სტეკში აღარავინ არის, ეს ნიშნავს, რომ ახლანდელი კრიმინალი არ მოკვდება, მას ვანიჭებთ სიკვდილის დროდ მაქსიმალურს პლიუს ერთს.

ახლა შევამოწმოთ თუ მივიღეთ ახალი ყველაზე გვიან მოკლული კრიმინალი. მაშასადამე თუ მაქსიმალურზე მეტი არაა ახლანდელის მოკლულის წუთი და ძველ მაქსიმალურზე (პასუხზე) მეტია, ახალი ყველაზე დიდხანს გადარჩენილი(რომელიც მოკვდა რაღაც ეტაპზე, მაგრამ მის შემდეგ წუთზე აღარავინ მომკვდარა) გვყოლია და ესაა ამ დროისთვის პასუხი.

ბოლოს წინა ეტაპზე სტეკიდან უნდა ამოვყაროთ მის წინ მდგომი ყველა კრიმინალი, რომელიც იმავე დროს მოკვდა ან უფრო ადრე ვიდრე ეს უკანასკნელი. მათი განხივა აღარ გვჭირდება.

საბოლოოდ ახლანდელ კრიმუნალს ვაგდებთ სტაკში და ვუწერთ რომელ წუზე მოკვდა.

როდესაც ციკლი დასრულდება პასუხში გვიწერია ბოლო წუთი, რომელზეც ვინმე მოკვდა, შესაბამისად ამას პლიუს ერთი იქნება საბოლოო პასუხი.

კოდი მაგალითისთვის:

#include <stack>
#include <string>
#include <iostream>

using namespace std;

int main() {
	stack <pair<int, int>> stk;
	int N;
	cin >> N;
	int ans = -1;

	for (int i = 0; i<N; ++i) {
		int curr_psycho;
		int killed = 0;
		cin >> curr_psycho;
		while (!stk.empty() && stk.top().first < curr_psycho) {
			killed = stk.top().second + 1;
			stk.pop();

		}
		//this criminal won’t die
		if (stk.empty()) {
			killed = N + 1;
		}
		
		//we have new criminal with survival record(who didn’t surive)
		if (killed <= N && killed > ans)
			ans = killed;

		while (!stk.empty() && stk.top().second <= killed){
			stk.pop();
		}

		stk.push({ curr_psycho, killed });
	}
	cout << ans + 1 << endl;
}