using c++ Write a programme that: reads the description of buildings from the standard input,determines the minimum number of posters needed to entirely cover their north faces,writes out the outcome to the standard output?

  • برمجة سي بلس بلس
  • برمجة

All the buildings in the east district of Byteburg were built in accordance with the old arbitecture: they stand next to each other with no spacing inbetween. Together they form a very long chain of buildings of diverse height, extending from east to west.The mayor of Byteburg, Byteasar, has decided to have the north face of the chain covered with posters. Byteasar ponders over the minimum number of posters sufficient to cover the whole north face. The posters have rectangular shape with vertical and horizontal sides. They cannot overlap, but may touch each other, i.e. have common points on the sides. Every poster has to entirely adjoin the walls of certain buildings and the whole surface of the north face has to be covered.

Questions:

 

Write a programme that:

1-reads the description of buildings from the standard input,

2-determines the minimum number of posters needed to entirely cover their north faces

3-writes out the outcome to the standard output.

Input:

The first line of the standard input contains one integer N (1 <= N <= 250000), denoting the number of buildings the chain comprises of. Each of the following N lines contains two integers Di and Wi (1 <= Di, Wi <=109), separated by a single space, denoting respectively the length and height of the i-th building in the row.

Output:

The first and only line of the standard output should contain one integer, the minimum number of rectangular posters that suffice to cover the north faces of the buildings.

 

الأجوبة

#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 5e5 + 2;
int n, d[N], res, h[N];
stack<int> s;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", d + i, h + i);
		if (s.empty()) {
			res++;
			s.push(h[i]);
		} else {
			while (s.top() > h[i]) {
				s.pop();
				if (s.empty())
					break;
			}
			if (s.empty()) {
				res++;
				s.push(h[i]);
			} else {
				if (s.top() == h[i])
					continue;
				else {
					res++;
					s.push(h[i]);
				}
			}
		}
	}
	cout << res;
	return 0;
}
سجل الدخول لتستطيع الإجابة
هل كان المحتوى مفيد؟

0 نعم

0 لا

أسئلة مشابهة

the number of different possible color assignments. The number can be quite big, so the King has requested to know the answer modulo 1000000007?
Domino piling program using c++
c++ problem Stones on the Table There are n stones on the table in a row, each of them can be red, green or blue. Count the minimum number of stones to take from the table so that any two neighboring stones had
Write a program in C# Sharp to accept a grade and declare the equivalent description

القوائم الدراسية التي ينتمي لها السؤال

معلومات ذات صلة

تبحث عن مدرس اونلاين؟

ابحث عن مدرسك
محتاج مساعدة باختيار المدرس الافضل؟ تواصل مع فريقنا الان لمساعدتك بتأمين افضل مدرس
ماهو التخصص الذي تبحث عنه؟
اكتب هنا...