Can somebody give some hints? problem name : students council ( from cf edu section)
Regards.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | Dominater069 | 151 |
9 | maroonrk | 151 |
Can somebody give some hints? problem name : students council ( from cf edu section)
Regards.
Name |
---|
*In this problem we need to maximize the number of councils we need to search for that maximum value of x that satifies the given condition.
*In the worst case the total councils may be 0 and in the best case total councils may be (sum of students/k), so we need to search the maximum value between these two numbers.
*the trend its shows will be T,T,T,F,F,F.. we need to find the last true. so I applied binary search and it got accepted.
//sorry for my bad english
how are you checking if x councils are possible or not
To check if it is possible to create x councils, each consists of k students. lets take all possible students from each group I can take maximum of x students at the end if I get >= (x*k) students then x councils can be created.
bool is(int x,vector &arr,int k) { int sum=0; //to track of maximum students I can take to create x councils
for(int i=0;i<arr.size();i++) { sum+=min(x,arr[i]);//I can take maximum of x students from each group }
if(sum>=(x*k)) return true;
else return false; }
thank you bro
thanks bro
Thanks, i'm still wondering how you come up with this idea bro
You can note that if you can form K > 1 councils, then you can form K — 1. So binary search will help.
possible(m) tell us if is possible to form at least m councils.
To construct possible(m) here is a hint:
sort groups by size, then find out if you can apply a greedy algorithm.