Решение задачи Экзамен в БерГУ (упрощённая версия) с Codeforces

Без пояснения   Просмотров: 1028

Единственное отличие этой версии от усложнённой — это ограничения.

В Берляндском государственном университете началась сессия. Многие студенты уже сдают экзамены.

Совсем скоро Полиграф Полиграфович примет экзамен у группы из n студентов. Студенты будут сдавать экзамен подряд один за другим в порядке от 1-го до n-го. Процесс сдачи происходит следующим образом:

i-й студент подходит к преподавательскому столу и тянет билет;
если студент понимает, что билет для него слишком сложный, то он отказывается отвечать и уходит домой (этот процесс происходит настолько быстро, что считается, что на него не расходуется время);
если студент посчитал, что билет несложный, то он тратит ровно ti минут на сдачу экзамена, после чего он получает отметку и уходит домой.
Студенты сдают экзамен один за другим без перерывов. Полиграф Полиграфович в один момент времени принимает экзамен у одного студента.

Длительность всего экзамена составляет M минут (maxti≤M), поэтому чем ближе студент находится к концу списка, тем больше вероятность того, что он не успеет сдать экзамен.

Ваша задача состоит в том, чтобы для каждого студента i определить минимальное количество студентов, которые должны уйти домой, чтобы i-й студент гарантированно успел полностью сдать экзамен.

Для каждого студента i ответ надо искать независимо, то есть если при нахождении ответа для студента i1 про какого-то студента j выяснилость, что он должен уйти, то при нахождении ответа для i2 (i2>i1) студент j не обязательно должен уйти домой.

Код 

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,sum=0;
	cin>>n>>m;
	vector<int> a,b;
	for(int i=0;i<n;i++)
	{
		int e;
		cin>>e;
		sum=sum+e;
		sort(a.begin(),a.end());
		int k=sum;
		int l=0,s=1;
		while(k>m)
		{
			k=k-a[a.size()-s];
			s++;
			l++;
		}
		b.push_back(l);
		a.push_back(e);
	}
	for(int i=0;i<b.size();i++)
		cout<<b[i]<<" ";
	return 0;	
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp