Horror Movie | HORROR

Problem Link

Horror Movie

Setter: Ayush Kumar
Tester: Ramandeep Singh
Editorialist: Ayush Kumar

Difficulty

Easy

problem

Sidharth, being a big fan of horror movies planned to watch horror movie along with his friend Sahu.
Each movie has an associated horror yield. Sidharth has a list of N movies and Sahu has another list of N movies. Sidharth and Sahu agree to choose some positive integer i \leq N and then Sidharth watches the i-th movie from his list and Sahu watches i-th movie from his own list. Sidharth wants the combined horror yield of the movies watched by him and Sahu to be as maximum as possible. Sahu doesn’t want to be scared a lot. So, among all choices which maximize combined horror yield, they would select the one which minimizes the horror yield experienced by Sahu.

Since they were unable to decide, they approached their friend Debo for help. But since Debo was busy with Videhi, he asked you to do this in place of him. You have to solve this for T test cases.

Explanation

This is a simple implementation-based question. The whole objective is to find the indices which have the maximum sum of horror yield and among that find the index which has the minimum value of bi

(Horror yield for Sahu). The implementation may vary depending upon how one wants to implement it.

Consider sum to be the current sum of horror yield, cur be the current horror yield for Sahu and ind be the current answer index.

While traversing from 1to n, we will check that whether the sum is less than ai+bi.
If yes, update sum with ai+bi, cur with bi and ind with i.

Else if the sum comes out to be equal to ai+bi, we will check whether cur is greater than bi. If yes, we will update cur with bi and ind with i
.
Else, we will traverse further. Initially sum can be initialized with INT_MIN, cur with INT_MAX and ind with −1.
.

Time Complexity

O(n) per test case

solution


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

#define ll long long

int main()
{
    ll t;
    cin >> t;
    while (t--)
    {
        ll n = 1e9;
        cin >> n;
        ll movies[n];

        for (ll i = 0; i < n; i++)
            cin >> movies[i];

        ll movies2[n];

        for (ll i = 0; i < n; i++)
            cin >> movies2[i];

        long long horrorMax = 0;

        for (ll i = 0; i < n; i++)
        {
            long long horror = movies[i] + movies2[i];
            horrorMax = max(horrorMax, horror);
        }
        ll least = INT_MAX;
        ll index;

        for (ll i = 0; i < n; i++)
            if (movies[i] + movies2[i] == horrorMax && movies2[i] < least)
            {
                least = movies2[i];
                index = i;
            }
        cout << index + 1 << "\n";
    }
    return 0;
}