Answer to Question #155554 in C++ for Abu Ubayda

Question

Aarong is a chain of Bangladeshi department stores and owned by BRAC. It provides the market linkage through different retail outlets. Recently, they have decided to build several storehouse along the highway, each one located at an outlets and supplying several of the outlets with the needed goods. Generally, these storehouses should be placed so that the average distance between a outlet and its assigned storehouse is minimized. You are to write a program that computes the optimal positions and assignments of the storehouses.

To make this more precise, the management of Aarong has issued the following specification: You will be given the positions of n restaurants along the highway as n integers d1 < d2 <……< dn (these are the distances measured from the company’s head outlet, which happens to be at the same highway). Furthermore, a number k (k ≤ n) will be given, the number of storehouse to be built.

The k storehouses will be built at the locations of k different restaurants. Each outlet will be assigned to the closest storehouse, from which it will then receive its supplies. To minimize shipping costs, the total distance sum, defined as

must be as small as possible.

Write a program that computes the positions of the k storehouses, such that the total distance sum is minimized.

Input Format

The input file contains several descriptions of Aarong chains. Each description starts with a line containing the two integers n and k. Following this will n lines containing one integer each, giving the positions di of the restaurants, ordered increasingly.

The input file will end with a case starting with n = k = 0. This case should not be processed.

Constraints

1 ≤ n ≤ 200

1 ≤ k ≤ 30

k ≤ n.

Output Format

For each chain, first output the number of the chain. Then output an optimal placement of the storehouse as follows: for each storehouse output a line containing its position and the range of outlets it serves. If there is more than one optimal solution, output any of them. After the storehouse descriptions output a line containing the total distance sum, as defined in the problem text. Output a blank line after each test case.

Sample Input 0

6 3
5
6
12
19
20
27
0 0

Sample Output 0

Chain 1
Total distance sum = 8

Answer 1

#include<bits/stdc++.h>

using namespace std;

int main() {
   int m, n, num;
  
   cin >> n >> m;
  
   int arr[n];
  
   for(int i=0;i<n;i++){
       cin >> arr[i];
   }
  
   for(int query=0; query<m; query++){
       int i, j, k;
       cin >> i >> j >> k;
      
       if(i == 1)
           arr[j] = k;
       if(i == 2){
           int* i1;
       i1 = max_element(arr + j, arr + k + 1);
      
       cout << *i1 << endl;
       }
   }
}