Hay n personas y dos máquinas de votar idénticas. También se nos da una array a[] de tamaño n tal que a[i] almacena el tiempo requerido por la i-ésima persona para ir a cualquier máquina, marcar su voto y regresar. En un instante de tiempo, solo una persona puede estar allí en cada una de las máquinas. Dado un valor x, que define el tiempo máximo permitido durante el cual las máquinas están operativas, verifique si todas las personas pueden emitir su voto o no.
Ejemplos:
Input : n = 3, x = 4
a[] = {2, 4, 2}
Output: YES
There are n = 3 persons say and maximum
allowed time is x = 4 units. Let the persons
be P0, P1, and P2 and two machines be M0 and M1.
At t0: P0 goes to M0
At t0: P1 goes to M1
At t2: M0 is free, P2 goes to M0
At t4: both M0 and M1 are free and all 3 have
given their vote.
Método 1
Sea sum el tiempo total empleado por todas las n personas. Si la suma <=x, entonces la respuesta obviamente será SÍ. De lo contrario, debemos verificar si la array dada se puede dividir en dos partes, de modo que la suma de la primera parte y la suma de la segunda parte sean ambas menores o iguales a x. El problema es similar al problema de la mochila . Imagina dos mochilas cada una con capacidad x. Ahora encuentre el máximo de personas que pueden votar en cualquier máquina, es decir, encuentre la suma máxima del subconjunto para una mochila de capacidad x. Sea esta suma s1. Ahora, si (suma-s1) <= x, entonces la respuesta es SÍ, de lo contrario, la respuesta es NO.
C++
// C++ program to check if all people can
// vote using two machines within limited
// time
#include<bits/stdc++.h>
using namespace std;
// Returns true if n people can vote using
// two machines in x time.
bool canVote(int a[], int n, int x)
{
// dp[i][j] stores maximum possible number
// of people among arr[0..i-1] can vote
// in j time.
int dp[n+1][x+1];
memset(dp, 0, sizeof(dp));
// Find sum of all times
int sum = 0;
for (int i=0; i<=n; i++ )
sum += a[i];
// Fill dp[][] in bottom up manner (Similar
// to knapsack).
for (int i=1; i<=n; i++)
for (int j=1; j<=x; j++)
if (a[i] <= j)
dp[i][j] = max(dp[i-1][j],
a[i] + dp[i-1][j-a[i]]);
else
dp[i][j] = dp[i-1][j];
// If remaining people can go to other machine.
return (sum - dp[n][x] <= x);
}
// Driver code
int main()
{
int n = 3, x = 4;
int a[] = {2, 4, 2};
canVote(a, n, x)? cout << "YES\n" :
cout << "NO\n";
return 0;
}
Java
// Java program to check if all people can
// vote using two machines within limited
// time
public class Main
{
// Returns true if n people can vote using
// two machines in x time.
static boolean canVote(int[] a, int n, int x)
{
// dp[i][j] stores maximum possible number
// of people among arr[0..i-1] can vote
// in j time.
int[][] dp = new int[n + 1][x + 1];
for(int i = 0; i < n + 1; i++)
{
for(int j = 0; j < x + 1; j++)
{
dp[i][j] = 0;
}
}
// Find sum of all times
int sum = 0;
for (int i = 0; i < n; i++ )
sum += a[i];
// Fill dp[][] in bottom up manner (Similar
// to knapsack).
for (int i = 1; i < n; i++)
for (int j = 1; j <= x; j++)
if (a[i] <= j)
dp[i][j] = Math.max(dp[i - 1][j], a[i] + dp[i - 1][j - a[i]]);
else
dp[i][j] = dp[i - 1][j];
// If remaining people can go to other machine.
return (sum - dp[n][x] >= x);
}
public static void main(String[] args) {
int n = 3, x = 4;
int[] a = {2, 4, 2};
if(canVote(a, n, x))
{
System.out.println("YES");
}
else{
System.out.println("NO");
}
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program to check if all people can
# vote using two machines within limited
# time
# Function returns true if n people can vote
# using two machines in x time.
def canVote(a, n, x):
# dp[i][j] stores maximum possible number
# of people among arr[0..i-1] can vote
# in j time.
dp = [[0] * (x + 1) for _ in range(n + 1)]
a = a[:]
a.append(0)
# Find sum of all times
sm = 0
for i in range(n + 1):
sm += a[i]
# Fill dp[][] in bottom up manner
# (Similar to knapsack).
for i in range(1, n + 1):
for j in range(1, x + 1):
if a[i] <= j:
dp[i][j] = max(dp[i - 1][j], a[i] +
dp[i - 1][j - a[i]])
else:
dp[i][j] = dp[i - 1][j]
# If remaining people can go to other machine.
return (sm - dp[n][x]) <= x
# Driver Code
if __name__ == "__main__":
n = 3
x = 4
a = [2, 4, 2]
print("YES" if canVote(a, n, x) else "NO")
# This code is contributed
# by vibhu4agarwal
C#
// C# program to check if all people can
// vote using two machines within limited
// time
using System;
class GFG {
// Returns true if n people can vote using
// two machines in x time.
static bool canVote(int[] a, int n, int x)
{
// dp[i][j] stores maximum possible number
// of people among arr[0..i-1] can vote
// in j time.
int[,] dp = new int[n + 1, x + 1];
for(int i = 0; i < n + 1; i++)
{
for(int j = 0; j < x + 1; j++)
{
dp[i, j] = 0;
}
}
// Find sum of all times
int sum = 0;
for (int i = 0; i < n; i++ )
sum += a[i];
// Fill dp[][] in bottom up manner (Similar
// to knapsack).
for (int i = 1; i < n; i++)
for (int j = 1; j <= x; j++)
if (a[i] <= j)
dp[i, j] = Math.Max(dp[i - 1, j],
a[i] + dp[i - 1, j - a[i]]);
else
dp[i, j] = dp[i - 1, j];
// If remaining people can go to other machine.
return (sum - dp[n, x] >= x);
}
// Driver code
static void Main()
{
int n = 3, x = 4;
int[] a = {2, 4, 2};
if(canVote(a, n, x))
{
Console.Write("YES");
}
else{
Console.Write("NO");
}
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// Javascript program to check if all people can
// vote using two machines within limited
// time
// Returns true if n people can vote using
// two machines in x time.
function canVote(a, n, x)
{
// dp[i][j] stores maximum possible number
// of people among arr[0..i-1] can vote
// in j time.
let dp = new Array(n+1);
for(let i = 0; i < n + 1; i++)
{
dp[i] = new Array(x + 1);
for(let j = 0; j < x+1; j++)
{
dp[i][j] = 0;
}
}
// Find sum of all times
let sum = 0;
for (let i=0; i<n; i++ )
sum += a[i];
// Fill dp[][] in bottom up manner (Similar
// to knapsack).
for (let i = 1; i <= n; i++)
for (let j = 1; j <= x; j++)
if (a[i] <= j)
dp[i][j] = Math.max(dp[i-1][j],
a[i] + dp[i-1][j-a[i]]);
else
dp[i][j] = dp[i-1][j];
// If remaining people can go to other machine.
return (sum - dp[n][x] <= x);
}
let n = 3, x = 4;
let a = [2, 4, 2];
if(canVote(a, n, x))
{
document.write("YES");
}
else{
document.write("NO");
}
// This code is contributed by decode2207.
</script>
Producción:
YES
Tiempo Complejidad: O(x * n)
Espacio Auxiliar: O(x * n)
Este artículo es una contribución de Ekta Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Método 2
El método anterior usa O(x * n) espacio extra, aquí damos un método que usa O(n) espacio extra.
La idea es ordenar la array y luego verificar si podemos obtener dos arrays que puedan ser un subarreglo que pueda estar entre el inicio y el final de la array, de modo que su suma sea menor o igual que x y la suma de los elementos restantes también sea menor. que x.
Usamos el prefijo sum para este propósito. Establecemos i y j y verificamos si la array ordenada entre i a j – 1 da suma <= x y los elementos restantes también suman suma <= x.
C++
// C++ program to check if all people can
// vote using two machines within limited
// time
#include<bits/stdc++.h>
using namespace std;
// Returns true if n people can vote using
// two machines in x time.
bool canVote(vector<int> a, int n, int x)
{
// calculate total sum i.e total
// time taken by all people
int total_sum = 0;
for(auto x : a){
total_sum += x;
}
// if total time is less than x then
// all people can definitely vote
// hence return true
if(total_sum <= x)
return true;
// sort the vector
sort(a.begin(), a.end());
// declare a vector presum of same size
// as that of a and initialize it with 0
vector<int> presum(a.size(), 0);
// prefixsum for first element
// will be element itself
presum[0] = a[0];
// fill the array
for(int i = 1; i < presum.size(); i++){
presum[i] = presum[i - 1] + a[i];
}
// Set i and j and check if array
// from i to j - 1 gives sum <= x
for(int i = 0; i < presum.size(); i++){
for(int j = i + 1; j < presum.size(); j++){
int arr1_sum = (presum[i] +
(total_sum - presum[j]));
if((arr1_sum <= x) &&
(total_sum - arr1_sum) <= x)
return true;
}
}
return false;
}
// Driver code
int main()
{
int n = 3, x = 4;
vector<int>a = {2, 4, 2};
canVote(a, n, x)? cout << "YES\n" :
cout << "NO\n";
return 0;
}
Java
// Java program to check if all people can
// vote using two machines within limited
// time
import java.io.*;
import java.util.*;
class GFG {
// Returns true if n people can vote using
// two machines in x time.
public static boolean canVote(int a[], int n, int x)
{
// calculate total sum i.e total
// time taken by all people
int total_sum = 0;
for (int z : a) {
total_sum += z;
}
// if total time is less than x then
// all people can definitely vote
// hence return true
if (total_sum <= x)
return true;
// sort the array
Arrays.sort(a);
// declare a array presum of same size
// as that of a and initialize it with 0
int presum[] = new int[a.length];
// prefixsum for first element
// will be element itself
presum[0] = a[0];
// fill the array
for (int i = 1; i < presum.length; i++) {
presum[i] = presum[i - 1] + a[i];
}
// Set i and j and check if array
// from i to j - 1 gives sum <= x
for (int i = 0; i < presum.length; i++) {
for (int j = i + 1; j < presum.length; j++) {
int arr1_sum
= (presum[i] + (total_sum - presum[j]));
if ((arr1_sum <= x)
&& (total_sum - arr1_sum) <= x)
return true;
}
}
return false;
}
// Driver Code
public static void main(String[] args)
{
int n = 3, x = 4;
int a[] = { 2, 4, 2 };
if (canVote(a, n, x) == true)
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python3 program to check if all people can
# vote using two machines within limited
# time
# Returns true if n people can vote using
# two machines in x time.
def canVote(a, n, x):
# calculate total sum i.e total
# time taken by all people
total_sum = 0
for i in range(len(a)):
total_sum += a[i]
# if total time is less than x then
# all people can definitely vote
# hence return true
if(total_sum <= x):
return True
# sort the list
a.sort()
# declare a list presum of same size
# as that of a and initialize it with 0
presum = [0 for i in range(len(a))]
# prefixsum for first element
# will be element itself
presum[0] = a[0]
# fill the array
for i in range(1, len(presum)):
presum[i] = presum[i - 1] + a[i]
# Set i and j and check if array
# from i to j - 1 gives sum <= x
for i in range(0, len(presum)):
for j in range(i + 1, len(presum)):
arr1_sum = (presum[i] + (total_sum - presum[j]))
if((arr1_sum <= x) and
(total_sum - arr1_sum) <= x):
return True
return False
# Driver code
n = 3
x = 4
a = [2, 4, 2]
if(canVote(a, n, x)):
print("YES")
else:
print("NO")
# This code is contributed by ashutosh450
Complejidad de tiempo: O(n * n) // dado que dos bucles están anidados uno dentro del otro, tienen una complejidad de tiempo de n*n
Espacio auxiliar: O(n) // ya que un vector adicional de tamaño igual a la longitud de la array
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA