Блог пользователя jerseyguy

Needed some hints to this problem
Автор jerseyguy, история, 3 года назад, По-английски

Can somebody give some hints? problem name : students council ( from cf edu section)

Regards.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • First of all if we need to build x councils each consists of k students, then from each group we can take atmost x students. So in the end if we get more than (x*k) students from the group we can build x coucils.

*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

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how are you checking if x councils are possible or not

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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; }

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить