Help with a code for the problem below:

general
, ,
1

image
image837Ă—519 21 KB

My Code:


#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N;
    cin>>N;
    int Ai[N], Bi[N];
    int sumofA=0;
    int sumofboth=1;
    for(int i=0;i<N;i++)
    {
         cin>>Ai[i]>>Bi[i];
         int x; //cities he gives speeches in
         //N-x cities he does not give any speeches
         //sum of Ai[_] in (N-x) cities should be lesser than sum of Ai[_] and Bi[_] in x cities.
         // x is least => Ai+ Bi should be maximum in the cities he should give speech
         int sum[N];
         sum[i]=Ai[i]+Bi[i];
         sort(sum,sum+N);
         sort(Ai,Ai+N);
         reverse(Ai,Ai+N);
         while(sumofboth>sumofA)
         {
              sumofA=sumofA+Ai[i];
              sumofboth=sumofboth+sum[i];
              i++;
         }
         x=i;
         cout<<x;
    }
}

The above is giving me the wrong answer. I suspect that something might be wrong with my declaring “sumofboth=1” but I couldn’t think of any other way for going forward with this code. (the while loop wouldn’t work otherwise) Could someone please give any suggestions?

2

@swastimishra01
The logic is just make vector of pair and put {A[i]+B[i],A[i]} in it
then sort it and then proceed greedily.

1 Like
3

“Proceed greedily”, is this an algorithm? I’m fairly new to cp, so I am unaware of these terms. Do you mind sharing some resources? Thank you.

4

@swastimishra01
No problem,
Greedy means like picking the element which benefits u.
if u want the whole code plzz send the question link

5

@dpcoder_007