Решение задачи Салем и палочки с Codeforces

Без пояснения   Просмотров: 295

Салем дал вам n палочек c целыми положительными длинами a1,a2,…,an.

Для каждой палочки, вы можете поменять её длину на любую другую положительную целую длину (то есть уменьшить или увеличить её). Стоимость изменения у палочки длины a на длину b равна |a−b|, где |x| обозначает модуль x.

Длина палочки ai называется почти хорошей для некоторого целого t, если |ai−t|≤1.

Салем просит вас поменять длины у каких-то палочек (возможно у всех или у никаких) так, что длины всех палочек будут почти хорошими для некоторого целого положительного t, а суммарная стоимость всех изменений будет минимально возможной. Значение t заранее не зафиксировано и вы можете выбрать его как произвольное целое положительное число.

В качестве ответа, выведите значение t и минимальную стоимость всех изменений. Если существует несколько оптимальных t, выведите любое из них.

Код 

#include<iostream>
using namespace std;
int a[1000+10];
int main(){
	
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	int t,ans=10000000;
	for(int i=1;i<=102;i++){
		int tmp=0;
		for(int j=0;j<n;j++){
			if(abs(a[j]-i)!=0)	tmp+=abs(a[j]-i)-1;
		}
		if(tmp<ans){
			ans=tmp;
			t=i;
		}
	}
	cout<<t<<" "<<ans<<endl;
	return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 mycod   [email protected]  Карта сайта   Правообладателям