## InterviewStreet Flowers Challenge

### Problem Statement

There are k friends who want to buy N flowers. Each flower has some cost c

_{i}. But there is condition that the price of flowers changes for customer who had bought flowers before. More precisely if a customer has already bought x flowers, he should pay (x+1)*c_{i}dollars to buy flower number i. What is the minimum amount you have to pay to buy all N flowers?**Ex Input :**

**Output :**

3 3 13

2 5 6

So first line contains n and k and next line contain ci, cost of ith flower.

### Algorithm

1) Arrange all the cost in an increasing sequence...d1,d2..dn

2) Allot from end nth flower to friend 1, n-1 flower to friend 2 and so on..until k after which cost factor would be 2 and hence flower n-k would cost 2*d(n-k) to friend 1 and n-k-1 flower will cost 2*d(n-k-1) to friend 2 and so on until all flowers are bought by somebody.

If you have a different approach in mind, please share it in comments section.

### Solution

#include<iostream>

#include<set>

using namespace std;

int main()

{

int n,k;

cin >> n >> k;

if(k > n) k=n;

int i,x;

multiset<int> s;

multiset<int>::iterator it;

for(i=0;i<n;i++) {

cin >> x;

s.insert(x);

}

//start calculating cost

int factor = 0;

unsigned long long int cost=0;

int count = 0;

it = s.end(); it--;

while(count!=n)

{

if(count%k==0) factor+=1;

cost+=(*it * factor);

it--;

count++;

}

cout << cost << endl;

cin >> cost;

}

#include<set>

using namespace std;

int main()

{

int n,k;

cin >> n >> k;

if(k > n) k=n;

int i,x;

multiset<int> s;

multiset<int>::iterator it;

for(i=0;i<n;i++) {

cin >> x;

s.insert(x);

}

//start calculating cost

int factor = 0;

unsigned long long int cost=0;

int count = 0;

it = s.end(); it--;

while(count!=n)

{

if(count%k==0) factor+=1;

cost+=(*it * factor);

it--;

count++;

}

cout << cost << endl;

cin >> cost;

}

### Time Complexity

O(nlogn) to sort n cost numbers and O(n) to calculate the cost.O(n+nlogn) => O(nlogn)

Hence time complexity will be O(nlogn)

Question is not clear...please elaborate the connection of friends with output

ReplyDelete