Problema easy3 help!


#1

Questo problema mi sta distruggendo :tired_face:
Dopo aver provato con la soluzione con il doppio for, quella più facile, per controllare la somma massima pari, ho provato con quella in qui ordini i numeri pari e dispari e fai la somma dei più grandi. Bene fino a qui ci siamo, ma entrambi gli algoritmi sono troppo lenti… :thinking::thinking:
Io è da poco più di un anno che lavoro con C e per ordinare gli array conosco solo insertion selection e bubble sort.

#include <stdio.h>
#include <assert.h>

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	int n, i, j, t, r, maxp=-1, maxd=-1, c1=0, c2=0;
	scanf("%i", &n);
	int s[100000], a[100000], b[100000];
	assert(n>=1 && n<=100000);
	for(r=0; r<n; r++)
	{
		scanf("%i", &s[r]);
		assert(s[r]>=0 && s[r]<1000000);
		if(s[r]%2==0)
		{
			a[c1]=s[r];
			c1++;
		}
		if(s[r]%2!=0)
		{
			b[c2]=s[r];
			c2++;
		}
	}
	for (i=1; i<c1; i++)
	{
		t=a[i];
		for (j=i; j>0 && a[j-1]>t; --j)
			a[j]=a[j-1];
		a[j]=t;
	}
	for (i=1; i<c2; i++)
	{
		t=b[i];
		for (j=i; j>0 && b[j-1]>t; --j)
			b[j]=b[j-1];
		b[j]=t;
	}
	maxp=a[c1-1]+a[c1-2];
	maxd=b[c2-1]+b[c2-2];
	if(c1<1 && c2<1)
	{
		printf("-1");
	}
	else
	{
		if(maxp>maxd)
			printf("%i", maxp);
		if(maxd>maxp)
			printf("%i", maxd);
	}
	return 0;
}

questo è l’algoritmo con l’ordinamento pari e dispari.
Aiutoooo!!


#2

Per ordinare rapidamente( con un tempo medio pari a n log n) puoi usare la funzione della libreria algorithm sort(array,array+dimensione) per il c++. Per il c( correggetemi se mi sbaglio dato che ho sempre usato il c++) esiste la funzione qsort(vettore,10,sizeof(int),cmp); dove cmp è la funzione che indica come ordinare( il nome della funzione può essere qualsiasi, cmp sta per “compare”, confronta). In questo caso dovrebbe essere:

int cmp(const void *a, const void *b)
{
int primo = *(int *)a;
int secondo = *(int *)b;
if (primo > secondo) return 1;
if (primo < secondo) return -1;
return 0;
}

In c++ puoi aggiungere cmp se necessario. Per ulteriori dettagli leggi le pagine 38-39 della guida alla selezioni territoriali di A. Bugatti disponibile online.


#3

Sei sicuro ti serva ordinare per conoscere i 2 elementi maggiori tra i pari/dispari?


#4

Mi hai illuminato!!!
Non era necessario ordinarli :man_facepalming:
Grazie mille anche a battini per il consiglio.
Grazie ragazzi :+1:


#5

Non capisco perché l’ultimo testcase restituisce un output sbagliato…

#include <stdio.h>
#include <assert.h>
#define MAXN 100000

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	int n, sum, mp1=-1, mp2=-1, md1=-1, md2=-1, cp=0, cd=0, sp=0, sd=0;
	scanf("%i", &n);
	int s[MAXN];
	assert(n>=1 && n<=100000);
	for(int i=0; i<n; i++)
	{
		scanf("%i", &s[i]);
		assert(s[i]>=0 && s[i]<1000000);
	}
	if(n==1)
	{
		printf("-1");
	}
	if(n==2)
	{
		if((s[0]+s[1])%2==0)
		{
			sum=s[0]+s[1];
			printf("%i", sum);
		}
		if((s[0]+s[1])%2!=0)
		{
			printf("-1");
		}
	}
	if(n>2)
	{
		for(int k=0; k<n; k++)
		{
			if(s[k]>=mp1 && s[k]%2==0){
				mp1=s[k];
			}
			if(s[k]>=md1 && s[k]%2!=0){
				md1=s[k];
			}
			if(s[k]%2==0)
				cp++;
			if(s[k]%2!=0)
				cd++;
		}
		if(cp>=2 && cd>=2)
		{
			for(int l=0; l<n; l++)
			{
				if(s[l]>=mp2 && s[l]%2==0 && s[l]<mp1)
					mp2=s[l];
				if(s[l]>=md2 && s[l]%2!=0 && s[l]<md1)
					md2=s[l];
			}
		}
		if((cp==1 || cp==0) && cd>=2)
		{
			for(int l=0; l<n; l++)
			{
				if(s[l]>=md2 && s[l]%2!=0 && s[l]<md1)
					md2=s[l];
			}
			mp1=0;
			mp2=0;
		}
		if((cd==1 || cd==0) && cp>=2)
		{
			for(int l=0; l<n; l++)
			{
				if(s[l]>=mp2 && s[l]%2==0 && s[l]<mp1)
					mp2=s[l];
			}
			md1=0;
			md2=0;
		}
		sp=mp1+mp2;
		sd=md1+md2;
		if(sp>=sd)
			printf("%i", sp);
		if(sd>sp)
			printf("%i", sd);
	}
	return 0;
}

#6

Sbaglio o non consideri il caso in cui il massimo ed il secondo massimo siano uguali?


#7

Niente, avevi ragione te…
Avevo dimenticato quel caso :sweat_smile:
Adesso 100/100. Grazie :+1: