Sabotage

Soru için Enes Öncü'ye teşekkür ederiz.

Soru Metni:
Size N elemanlı bir dizi veriliyor. Bu diziden öyle bir altdizi siliniz ki sildiğiniz altdizi 1 ve N numaralı
indisleri içermesin ve geriye kalan elamanların ortalaması minimum olsun.
Cevabı noktadan sonra 3 basamağa kadar yazdırın.

3 <= N <= 100,000
1 <= dizinin herbir elemanı <= 10,000

Örnek Girdi

5
5 1 7 8 2

Örnek Çıktı

2.667

Açıklama:

3. ve 4. indisleri silersek ortalama 8/3 = 2.667 olur


Çözüm Metni:

Soru binary search sorusu. Cevabı binary search ile arayacağız.
Bir değeri denerken bu değerden küçük veya eşit bir ortalama olup olamayacağını kontrol edeceğiz.

Mesela cevabımız l ve r arasında olsun. Eğer (l+r)/2 den küçük eşit bir ortalama
bulabiliyorsak cevabımızın l ve (l+r)/2 arasında olduğunu biliriz. Aksi takdirde
cevabımız (l+r)/2 ve r aralığında olur.

Şimdi sorunun önemli kısmı olan bu kontrolün nasıl yapıldığını anlatacağım.

Ortalamanın bir K sayısından küçük eşit olabileceğini veya olamayacağını kontrol edelim. Dizideki
tüm elemalardan K çıkarttığımızda soruyu şuna dönüştürebiliriz: Dizimizden öyle bir altdizi
silelim ki 1. ve N. indisleri içermesin ve kalan elemanların toplamı 0 dan küçük eşit olsun.
Peki neden? Çünkü geriye a tane eleman kaldıgını varsayalım ve toplamları sum olsun. O zaman
dizinin elemanlarından K çıkartmadığımız durumda bu sayıların ortalaması (sum+a*K)/a<=K olurdu.
Eger sum<=0 şartı sağlanırsa (sum+a*K)/a<=K olur.
O zaman eğer sum'ın olabileceği en küçük değer 0 dan küçük eşitse ortalama K dan küçük eşit olabilir.
sum'ı en küçük yapmak için de dizide en büyük toplama sahip aralığı diziden sileriz. Bunu yapmak içinde
tüm elemanlarından K sayısı çıkarılmış dizideki 2 ve n-1 aralığında maximum toplama sahip altdiziyi buluruz.
Bunu Kadane yötemi gibi basit yöntemlerle yapabiliriz.



Çözüm Kodu:

#include <algorithm>
#include <iostream>
#include <cstdio>

#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )

using namespace std;

int n,arr[100005];

bool kontrol( double K ){

double sum=arr[1]+arr[n]-2*K;
double maxsubarray=-1999999999,now=0;

FP( i,2,n-1 ){
sum += arr[i]-K;
now += arr[i]-K;
maxsubarray = max( maxsubarray,now );
if( now<0 ) now = 0;
}

sum -= maxsubarray;

return sum<=0;

}

int main(){

freopen("sabotage.in","r",stdin);
freopen("sabotage.out","w",stdout);

cin >> n;
FP( i,1,n )
cin >> arr[i];

double l=0.0,r=1e9,mid;

for( int iteration=1;iteration<=100;iteration++ ){
mid = (l+r)/2;
if( kontrol( mid ) ) r = mid;
else l = mid;
}

printf("%.3lf\n",l);


}

Soruyu Göndermek için : http://usaco.org/index.php?page=viewproblem2&cpid=419