ACdream 발전소 (욕심)
3763 단어 욕심
ACdream 왕국 에는 어머니 강 이 있 는데 이 어머니 강 은 왕국 사람들 에 게 각종 생활 용 수 를 제공 합 니 다.강가 에 n 가구 가 살 고 있 고 가구 당 위 치 는 x [i] 입 니 다.경제 발전의 수요 로 인해 ACdream 은 이 어머니 강 에 수력 발전 소 를 세우 기로 결정 했다. 측량 을 통 해 이 수력 발전 소 는 구간 [a, b] 의 어 딘 가 에 만 x0 을 세 울 수 있다.발전소 에 오 는 사람들의 영향 을 줄 이기 위해 서 는 min {| x [i] - x0 | | 0 < = i < = n - 1} 이 가장 크 기 를 바 랍 니 다. 발전소 에서 가장 가 까 운 집 과 발전소 의 거리 가 가장 크 더 라 도.여러 조 의 답 이 있 으 면 출력 좌표 가 비교적 작은 것 이면 된다.Input
여러 조 의 데 이 터 는 각 조 의 데이터 에 대해 먼저 세 개의 정수 n (1 < = n < = 100), a, b (1 < = a < = b < = 10 ^ 9) 이 고 그 다음은 n 개의 정수 로 각 가구 의 좌 표를 나타 낸다.
Output
각 조 의 데이터 에 대해 하나의 정 수 를 출력 하여 가장 좋 은 발전소 의 좌표 위 치 를 나타 낸다.Sample Input
3 4 9 5 8 14 Sample Output
4
제목: 한 축 에 n 가구 가 있 고 [a, b] 사이 에 수력발전 소 를 건설 하여 위 치 를 구하 여 수력발전 소 가 가장 가 까 운 집에 서 가장 거리 가 멀다.분석: 가장 좋 은 곳 은 세 가지 상황 이 있다.단점단점3. 인접 한 두 집의 중심 점.
코드:
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
int n, a, b, c[105];
while(scanf("%d%d%d", &n, &a, &b) == 3) {
for(int i = 0; i < n; i++)
scanf("%d", &c[i]);
sort(c, c+n);
int mid = 0, ans, tt;
for(int i = 0; i < n-1; i++) {
if((c[i+1]-c[i]) > mid && (c[i]+c[i+1])/2 > a && (c[i]+c[i+1])/2 < b) {
mid = c[i+1]-c[i];
ans = c[i] + mid/2;
}
}
int ca = 1 << 30, cb = 1 << 30;
for(int i = 0; i < n; i++) {
int x = fabs(a-c[i]);
int y = fabs(b-c[i]);
ca = min(ca, x);
cb = min(cb, y);
}
if(ca >= mid/2 && ca >= cb)
ans = a;
if(cb > mid/2 && cb > ca)
ans = b;
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HPU - ACM 여름 훈련 2 주차 14 급 개인전: Problem D [욕심]Problem D Problem Description 그 러 고 보 니 해동 그룹 이 안팎 으로 어려움 을 겪 고 있 고 회사 의 원로 도 XHD 부부 만 남 았 다 고 한다.분명히 여러 해 동안 싸 운 상인 으로서...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.