C1. Exam in BerSU (easy version)
题目要求
给你一个 (n) 和 (m) ,然后接下来给出 (n) 个序列,这组序列中 (n_i) 代表第 (i) 位同志做题需要花费 (n_i) 分钟,而总时间只有 (m) 分钟。
每位同志的做题时间都会记录总时间,而且必须前一位同志做完了题,后一位才能开始,若到他没时间了,那他就失败了。
然而,我们的第 (i) 位老同志不想挂科,所以要你找出如果灭掉他前面的哪些同学,第 (i) 位老同志才会有时间答题而不挂科,这位老同志也怕得罪的人太多,所以尽可能得少灭掉他们
具体思路
题意已经蛮清楚得了,由于数据范围较小,( (1 le n le 100) ),所以直接上暴力,如下:
1、从头开始,一次是第 (1) 位、第 (2) 位、第 (...) 位
2、到了第 (i) 位后,先用 (m) 减去 (n_i) 那么得到了满足自己的答题时间后还剩下多少时间,然后分给前面的那些同学,当然是优先分给他们那些占用时间少的了。
所以这里进行排序,只排前 (i) 个哦,不包含第 (i) 个。
分给他们之后呢,如果不够分的话,就把剩下的那些同志挂科就可以了,
所以总共需要干掉第 (i) 个人之前的总人数 减去 那些不需要挂科的人 即可
总共的时间复杂度为 (O(N^3 LogN)) (10^7) 左右
AC代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> q;
int main ( void )
{
int n, s;
cin >> n >> s;
for ( int i = 0; i < n; i++ ) { int t; cin >> t; q.push_back ( t ); };
cout << 0 << ' ';
for ( int i = 1; i < n; i++ )
{
int cur = s - q[i];
sort ( q.begin(), q.begin() + i );
bool flag = true;
for ( int j = 0; j < i; j++ )
{
if ( ( cur -= q[j] ) < 0 ) { cout << i - j << ' '; flag = false; break; }; // WARNING
}
if ( flag ) cout << 0 << ' ';
}
return 0;
}