ACdream 발전소 (욕심)

3763 단어 욕심
F - ACdream 발전소 시간 제한: 2000 / 1000 MS (Java / Others) 메모리 제한: 128000 / 64000 KB (Java / Others) 제출 상태 문제 설명
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; }

좋은 웹페이지 즐겨찾기