Рубрики

Найти разделительную линию так, чтобы сумма значений слева и справа была равна

Рассмотрим n точек на декартовой координатной плоскости. Пусть точке (X i , Y i ) присвоено значение V i . Линия, параллельная оси y , называется хорошей линией разбиения, если сумма значений точек слева равна сумме значений точек справа. Обратите внимание, что если точка лежит на линии разбиения, то она не рассматривается по обе стороны от линии. Задача состоит в том, чтобы напечатать « Да», если существует хорошая линия раздела, иначе выведите « Нет» .

Пример:

Input: X[] = {-3, 5, 8}, Y[] = {8, 7, 9}, V[] = {8, 2, 10}
Output: Yes

x = c where 5 < c < 8 is a good partition
line as sum of values on both sides is 10.

Input: X[] = {-2, 5, 8, 9}, Y[] = {7, 7, 9, 8}, V[] = {6, 2, 1, 8}
Output: Yes

Подходить:

  1. Посчитайте значение по каждой x-координате. Это означает, что если есть несколько точек с одинаковыми координатами x, они будут рассматриваться как одна точка, и их значения будут добавлены.
  2. Начните с минимальной x-координаты и проверьте, выполняется ли одно из следующих условий в X i :
    • Сумма значений до i — 1 равна сумме значений от i + 1 до n .
    • Сумма значений до i равна сумме значений от i + 1 до n .
    • Сумма значений до i — 1 равна сумме значений от i до n .
  3. Если какое-либо из вышеуказанных условий выполняется для любой заданной точки, то линия существует.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  

const int MAX = 1000;

  
// Функция, которая возвращает true, если
// искомая строка существует

bool lineExists(int x[], int y[],

                int v[], int n)

{

  

    // Для обработки отрицательных значений из x []

    int size = (2 * MAX) + 1;

    long arr[size] = { 0 };

  

    // Обновляем arr [] так, чтобы arr [i] содержал

    // сумма всех v [j] такая, что x [j] = i

    // для всех допустимых значений j

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

        arr[x[i] + MAX] += v[i];

    }

  

    // Обновляем arr [i] так, чтобы arr [i] содержал

    // сумма подмассива arr [0 ... i]

    // из исходного массива

    for (int i = 1; i < size; i++)

        arr[i] += arr[i - 1];

  

    // Если все точки добавить к 0, то

    // линия может быть нарисована где угодно

    if (arr[size - 1] == 0)

        return true;

  

    // Если линия нарисована касаясь

    // крайние левые точки

    if (arr[size - 1] - arr[0] == 0)

        return true;

  

    for (int i = 1; i < size - 1; i++) {

  

        // Если линия нарисована как раз перед

        // текущая точка

        if (arr[i - 1] == arr[size - 1] - arr[i - 1])

            return true;

  

        // Если линия нарисована касанием

        // текущая точка

        if (arr[i - 1] == arr[size - 1] - arr[i])

            return true;

  

        // Если линия рисуется сразу после

        // текущая точка

        if (arr[i] == arr[size - 1] - arr[i])

            return true;

    }

  

    // Если линия нарисована касаясь

    // самые правые точки

    if (arr[size - 2] == 0)

        return true;

  

    return false;

}

  
// Код драйвера

int main()

{

    int x[] = { -3, 5, 8 };

    int y[] = { 8, 7, 9 };

    int v[] = { 8, 2, 10 };

    int n = sizeof(x) / sizeof(int);

  

    if (lineExists(x, y, v, n))

        cout << "Yes";

    else

        cout << "No";

  

    return 0;

}

Джава

// Java реализация подхода

class GFG 

{

static int MAX = 1000;

  
// Функция, которая возвращает true, если
// искомая строка существует

static boolean lineExists(int x[], int y[],

                          int v[], int n)

{

  

    // Для обработки отрицательных значений из x []

    int size = (2 * MAX) + 1;

    long []arr = new long[size];

  

    // Обновляем arr [] так, чтобы arr [i] содержал

    // сумма всех v [j] такая, что x [j] = i

    // для всех допустимых значений j

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

    {

        arr[x[i] + MAX] += v[i];

    }

  

    // Обновляем arr [i] так, чтобы arr [i] содержал

    // сумма подмассива arr [0 ... i]

    // из исходного массива

    for (int i = 1; i < size; i++)

        arr[i] += arr[i - 1];

  

    // Если все точки добавить к 0, то

    // линия может быть нарисована где угодно

    if (arr[size - 1] == 0)

        return true;

  

    // Если линия нарисована касаясь

    // крайние левые точки

    if (arr[size - 1] - arr[0] == 0)

        return true;

  

    for (int i = 1; i < size - 1; i++) 

    {

  

        // Если линия нарисована как раз перед

        // текущая точка

        if (arr[i - 1] == arr[size - 1] - arr[i - 1])

            return true;

  

        // Если линия нарисована касанием

        // текущая точка

        if (arr[i - 1] == arr[size - 1] - arr[i])

            return true;

  

        // Если линия рисуется сразу после

        // текущая точка

        if (arr[i] == arr[size - 1] - arr[i])

            return true;

    }

  

    // Если линия нарисована касаясь

    // самые правые точки

    if (arr[size - 2] == 0)

        return true;

  

    return false;

}

  
// Код драйвера

public static void main(String []args) 

{

    int x[] = { -3, 5, 8 };

    int y[] = { 8, 7, 9 };

    int v[] = { 8, 2, 10 };

    int n = x.length;

  

    if (lineExists(x, y, v, n))

        System.out.printf("Yes");

    else

        System.out.printf("No");

}
}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

MAX = 1000

  
# Функция, которая возвращает true, если
# требуемая строка существует

def lineExists(x, y, v, n) :

  

    # Для обработки отрицательных значений от x []

    size = (2 * MAX) + 1

    arr = [0] * size ; 

  

    # Обновите arr [] так, чтобы arr [i] содержал

    # сумма всех v [j] таких, что x [j] = i

    # для всех допустимых значений j

    for i in range(n) :

        arr[x[i] + MAX] += v[i]; 

  

    # Обновите arr [i] так, чтобы arr [i] содержал

    # сумма подмассива обр [0 ... i]

    # из исходного массива

    for i in range(1, size) :

        arr[i] += arr[i - 1]; 

  

    # Если все точки добавить к 0, то

    # линию можно провести где угодно

    if (arr[size - 1] == 0) :

        return True

  

    # Если линия нарисована касаясь

    # крайние левые точки

    if (arr[size - 1] - arr[0] == 0) :

        return True

  

    for i in range(1, size - 1) : 

  

        # Если линия нарисована непосредственно перед

        # текущая точка

        if (arr[i - 1] == arr[size - 1] - arr[i - 1]) :

            return True

  

        # Если линия нарисована касаясь

        # текущая точка

        if (arr[i - 1] == arr[size - 1] - arr[i]) :

            return True

  

        # Если линия рисуется сразу после

        # текущая точка

        if (arr[i] == arr[size - 1] - arr[i]) :

            return True

  

    # Если линия нарисована касаясь

    # самые правые возможные точки

    if (arr[size - 2] == 0) :

        return True

  

    return False

  
# Код драйвера

if __name__ == "__main__" :

  

    x = [ -3, 5, 8 ]; 

    y = [ 8, 7, 9 ]; 

    v = [ 8, 2, 10 ]; 

    n = len(x); 

  

    if (lineExists(x, y, v, n)) :

        print("Yes"); 

    else :

        print("No"); 

  
# Этот код предоставлен AnkitRai01

C #

// C # реализация подхода

using System;

      

class GFG 

{

static int MAX = 1000;

  
// Функция, которая возвращает true, если
// искомая строка существует

static Boolean lineExists(int []x, int []y,

                          int []v, int n)

{

  

    // Для обработки отрицательных значений из x []

    int size = (2 * MAX) + 1;

    long []arr = new long[size];

  

    // Обновляем arr [] так, чтобы arr [i] содержал

    // сумма всех v [j] такая, что x [j] = i

    // для всех допустимых значений j

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

    {

        arr[x[i] + MAX] += v[i];

    }

  

    // Обновляем arr [i] так, чтобы arr [i] содержал

    // сумма подмассива arr [0 ... i]

    // из исходного массива

    for (int i = 1; i < size; i++)

        arr[i] += arr[i - 1];

  

    // Если все точки добавить к 0, то

    // линия может быть нарисована где угодно

    if (arr[size - 1] == 0)

        return true;

  

    // Если линия нарисована касаясь

    // крайние левые точки

    if (arr[size - 1] - arr[0] == 0)

        return true;

  

    for (int i = 1; i < size - 1; i++) 

    {

  

        // Если линия нарисована как раз перед

        // текущая точка

        if (arr[i - 1] == arr[size - 1] - arr[i - 1])

            return true;

  

        // Если линия нарисована касанием

        // текущая точка

        if (arr[i - 1] == arr[size - 1] - arr[i])

            return true;

  

        // Если линия рисуется сразу после

        // текущая точка

        if (arr[i] == arr[size - 1] - arr[i])

            return true;

    }

  

    // Если линия нарисована касаясь

    // самые правые точки

    if (arr[size - 2] == 0)

        return true;

  

    return false;

}

  
// Код драйвера

public static void Main(String []args) 

{

    int []x = { -3, 5, 8 };

    int []y = { 8, 7, 9 };

    int []v = { 8, 2, 10 };

    int n = x.Length;

  

    if (lineExists(x, y, v, n))

        Console.WriteLine("Yes");

    else

        Console.WriteLine("No");

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

Yes

Рекомендуемые посты:

Найти разделительную линию так, чтобы сумма значений слева и справа была равна

0.00 (0%) 0 votes