Waiting for the turn -Editorial ||WATURN

editorial
,
1

PROBLEM LINK: Waiting for the turn | CodeChef

Problem Code: Waiting for the turn | CodeChef

Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef

Contest : Internal Contest CodeChef Adgitm Coding Competition | CodeChef

Author: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9

DIFFICULTY:

Easy-Med

PROBLEM:

There is a Shop in the Town which has a great Sale going on. There are long Queues at the shop to buy the goods but due to the overwhelming response of the sale shopkeeper can’t manage the crowd properly. So he decided that he will sell some limited amounts of the goods that are kk each day and sell only one item to the one person at a time. If a customer wants some more goods then he has to go back at the end of the queue and should wait for his turn again. Else he left the queue. You have to find the people left in the queue after the sale ends. There are NN number of people standing in the queue outside his shop waiting for their turn. Each person has to buy the ai number of the items where ii is the position of that person in the queue.

EXPLANATION:

Else if shopkeeper sold all the goods then we made a hashmap with key = arr[i] and value =arr[i]. Firstly we push all the elements in the queue data structure. And then mimic all the conditions as given in the question. If the value in front of any key becomes zero then remove it from the queue and if it is not then push it again ath end of the queue and reduce the value of that key by 1. And also reduce the value of K by 1. Keep it continue till the K becomes zero.And then print the queue to get the status of the queue and the order in which people left at the shop waiting in the queue.

SOLUTION:

C++:

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

void solve(int k, int n, vectorarr)
{
queueq;
map<int,int>mp;
for(int i=0; i<n; i++)
{
q.push(arr[i]);
mp[arr[i]]=arr[i];
}

while (k>0)
{
    int temp=q.front();
    q.pop();

    mp[temp]--;
    if(mp[temp]>0)
    q.push(temp);

    k--;
}

while(q.empty()==false)
{
    cout << q.front() << " ";
    q.pop();
}
cout << endl;

}
int main(){

int tc;
cin >> tc;
while (tc–)
{
int k,n;
cin >> k >> n;

vector<int>arr(n);
int sum=0;
for(int i=0; i<n; i++)
{
    cin >> arr[i];
    sum+=arr[i];
}

if(sum<k)
cout << "-1" << endl;
else
solve(k,n,arr);

}

return 0;
}