Answer to Question #100105 in Java | JSP | JSF for Madhuri

Question

A mother has children of varying ages in need of t-shirts. The mother has to distribute t-shirts with the following requirements:

Each child should get at least one t-shirt.
A child with an age higher than adjacent children should get more t-shirts than them.
How should the mother distribute such that total number of t-shirts is minimized?

Answer 1

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();

        int[] b = new int[n];
        b[0] = 0;
        b[n - 1] = 0;

        for (int i = 1; i < n - 1; i++) {
            if (a[i - 1] < a[i] && a[i] < a[i + 1])
                b[i] = 1;
            else if (a[i - 1] > a[i] && a[i] > a[i + 1])
                b[i] = -1;
            else b[i] = 0;
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            if (b[i] == 0 &&
                    ((i > 0 && a[i] > a[i - 1]) || (i < n - 1 && a[i] > a[i + 1]))) {

                int j1 = i - 1;
                while (j1 >= 0 && b[j1] != 0) j1--;

                int j2 = i + 1;
                while (j2 < n && b[j2] != 0) j2++;

                ans[i] = Math.max(i - j1, j2 - i) + 1;
                if (j1 >= 0) ans[j1] = 1;
                if (j2 < n) ans[j2] = 1;
                j1++;
                j2--;
                while (j1 < i) {
                    ans[j1] = ans[j1 - 1] + 1;
                    j1++;
                }
                while (j2 > i) {
                    ans[j2] = ans[j2 + 1] + 1;
                    j2--;
                }
            }
        }
        System.out.println("Final distribution:");
        for (int i = 0; i < n; i++)
            System.out.print(ans[i] + " ");
    }
}

/*
18
2 4 6 8 10 9 7 5 11 13 15 17 16 14 12 18 20 19

20
2 4 6 8 10 9 7 5 11 13 15 17 16 14 12 18 20 19 1 3
 */