필기시험 문제: 링 위의 화물 을 균등 하 게 분담 하 다 / 사탕 전달 문제 풀이 보고서

어 제 는 2013 년 알 리 바 바 인턴 캠퍼스 채용 필기시험 에 응시 했다.그 중 한 문 제 는 어디서 많이 본 것 처럼 답안 지 를 제출 하려 고 할 때 비로소 이것 이 수학 문제 라 는 것 을 어렴풋이 떠 올 렸 다.구체 적 으로 어떻게 했 는 지 기억 이 안 나 요.다시 잊 혀 지지 않도록 직접 써 보 세 요.
제목 참조:http://blog.csdn.net/hnmjiayou/article/details/8887127
해법 참조:http://blog.sina.com.cn/s/blog_75683c7f0100q4va.html
코드 참조:http://50vip.com/blog.php?i=223
타 오 바 오 판매자 가 있 습 니 다. 그 는 전국 에 n 개의 창 고 를 가지 고 있 습 니 다. 이 n 개의 창 고 는 마침 하나의 링 을 구성 하고 있 습 니 다. 다음 그림 에서 보 듯 이 그의 모든 창고 의 화물 수 는 다 릅 니 다. 지금 은 모든 창고 의 화물 수 를 똑 같이 하고 싶 습 니 다. 어떻게 운송 하면 전체적인 운송 원 가 를 가장 낮 출 수 있 습 니까? 그 중에서 한 번 의 운송 은 두 개의 인접 한 창고 사이 에서 만 발생 할 수 있 습 니 다.시험 설계 알고리즘.
분석:
우선, 제목 에 따 르 면 운송 은 두 개의 인접 한 창고 사이 에서 만 발생 할 수 있 지만 인접 한 두 창고 가 언제 운송 되 는 지, 운송 방향 이 어떤 지, 그리고 운송 횟수 를 규정 하지 않 았 다.
그러나 사실은 문 제 는 전체적인 운송 원 가 를 최소 화 하 는 것 만 요구 하기 때문에 우 리 는 인접 한 두 창고 간 에 누가 누구 에 게 운송 하 는 지, 그리고 인접 한 두 창고 간 의 총 수송량 에 만 관심 을 가 져 야 한다.이런 수송량 에 관심 을 가 질 필요 가 없다.
전체 운송 원 가 를 가장 낮 추 려 면 화물 은 인접 한 두 창고 사 이 를 왔다갔다 해 서 는 안 된다.즉, 인접 한 두 지점 사이 의 운송 방향 은 확실 하고 유일한 것 이다.그래서 우 리 는 그림 1 에서 인접 한 한 쪽 을 방향 이 있 는 것 으로 보고 이 방향 이 있 는 가중치 가 변경 에서 진행 해 야 할 총 운송 화물 량 이 라 고 정의 할 수 있다.
우 리 는 또한 이 문제 에 대한 묘 사 를 더욱 간소화 하고 추상 화 할 수 있다.우 리 는 만약 에 인접 한 두 변 의 운송 이 시계 방향 으로 진행 된다 면 이번 운송 의 가중치 가 바로 플러스 라 고 규정 할 수 있다.운송 이 시계 반대 방향 으로 진행 된다 면 운송 의 가 치 는 마이너스 다.가중치 의 절대 치 는 인접 한 두 점 사이 에 운송 되 는 화물 의 총량 을 나타 낸다.각 변 의 가 치 를 Pi 로 기록 하 다.그림 2 와 같다.

자, 여기까지 입 니 다. 우 리 는 문 제 를 P1 로 간략화 하 였 습 니 다. P2,...... Pn 의 조합 은 운송 후 각 노드 를 똑 같이 하 는 전제 에서 가장 작다.그 중에서 Pi 는 구간 [- total, total] 내 수치, total 은 n 개 노드 의 총 화물 량 을 나타 낸다.문 제 는 매 거 진 문제 로 바 뀌 었 지만, 사실상 이 길 은 불가능 하 다. 매 거 진 공간 이 너무 넓 기 때문이다.
이어서 우 리 는 제목 에 포 함 된 정 보 를 계속 발굴 할 것 이다.우 리 는 Gi 로 모든 창고 의 재 고량 을 표시 합 니 다.평균 화물 량 을 average 로 표시 하 다.그리고 리 = 기 - average 는 제 i 창고 재 고량 과 평균 재고 의 차 이 를 나타 낸다.그러면 Pi 와 Ri 는 다음 과 같은 조건 을 만족 시 켜 야 합 니 다.
0 = Pn + R1 - P1
0 = Pi-1+Ri - Pi （i≠1）
우 리 는 끊임없이 전달 함으로써 Pi (i ≠ 1) 를 P1 의 선형 변환 으로 표시 할 수 있다 는 것 을 발견 했다.령 P1 = x。있다:
P2 = x + R2；
P3 = x + R2 + R3；
P4 = x + R2 + R3 + R4;
P5 = x + R2 + R3 + R4 + R5;
....
우 리 는 다시 새로운 기 호 를 도입 했다.령:
Pi = x - Ti。그 중 T1 = 0 그리고 Ti = Ti-1 - Ri。
현재 을 최소 화 하 는 Pi 조합 문 제 를 구하 면 의 최소 x 의 값 을 구 하 는 문제 로 바 뀌 었 다.그 중에서 도 티 는 상수 다.n 개의 변 수 를 하나의 변수 로 줄 인 후에 검색 공간 이 크게 줄 어 든 것 을 발견 했다.[- total 에서 만, total] 구간 에서 x 를 검색 하면 됩 니 다.이 단계 에 이 르 러 우 리 는 검색 공간 을 크게 줄 였 지만 이 문 제 는 더욱 최적화 할 수 있다.
우 리 는 {Ti} 을 수치 에 따라 축 위 에 흩 어 놓 을 것 이다.관찰 분석 을 통 해 알 수 있 듯 이 x 가 {Ti} 의 중위 수 일 때 가 가장 작다.
x 의 확정 값 을 구 해 낸 후에파이 재 활용 = x - Ti 는 모든 변 의 가 치 를 미 룰 수 있 습 니 다.위의 토론 에서 알 수 있다.Pi 가 0 보다 크 면 창고 i 가 창고 i + 1 에 Pi 개 화물 을 운송 해 야 한 다 는 뜻 (i 가 n 이면 i 창고 가 1 창고 로 화물 을 운송 하 는 것 을 의미한다).Pi 가 0 보다 작 으 면 창고 i 가 창고 i - 1 로 | Pi | 개 화물 을 운송 하 는 것 을 나타 낸다 (i 가 1 이면 창고 i 가 창고 n 으로 화물 을 운송 하 는 것 을 나타 낸다).0 이면 조작 하지 않 는 다.
참조 코드:

#include <cstring>
#include <iostream>
#include <algorithm>
        
using namespace std;
const int X = 1000005;
typedef long long ll;
ll sum[X],a[X];
ll n;
ll Abs(ll x){
    return max(x,-x);
}
int main(){
    //freopen("sum.in","r",stdin);
    while(cin>>n){
        ll x;
        ll tot = 0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            tot += a[i];
        }
        ll ave = tot/n;
        for(int i=1;i<n;i++)
            sum[i] = a[i]+sum[i-1]-ave;
        sort(sum+1,sum+n);
        ll mid = sum[n/2];
        ll ans = Abs(mid);
        for(int i=1;i<n;i++)
            ans += Abs(sum[i]-mid);
        cout<<ans<<endl;//  ans         。
    }
    return 0;
}

상기 코드 에서 수출 한 ans 는 전체적인 운송 대가 이다.구체 적 인 운송 방안 을 얻 으 려 면 저장 공간 저장 정렬 전의 sum 값 을 따로 열 어야 합 니 다.mid 값 을 가 져 온 후 sum [i] 를 통 해 모든 창고 에서 실 행 된 운송 작업 을 추정 합 니 다.