Disk Scheduling

Each input file only contains one test case.
The first line contains two integer n, m (1 ≤ n ≤ $10^6$ , 1 ≤ m ≤ $10^9$ ), indicating the length of the track sequence and the number of the current magnetic head.
The second line contains n integers $a_1,a_2,...,a_n$ (1 ≤ $a_i$ ≤ $10^9$ ), indicating the track sequence.

C++14(g++5.4) 解法, 执行用时: 338ms, 内存消耗: 13704K, 提交时间: 2019-12-08 20:07:15

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int INF=2e9+10;
int n,m;
int a[maxn];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    a[++n]=m;
    sort(a+1,a+n+1);
    a[0]=a[++n]=INF;
    int pos=0;
    for(int i=0;i<=n;i++){
        if(a[i]==m){
            pos=i;
            break;
        }
    }
    ll res=0;
    int pre=pos-1,nex=pos+1;
    for(int i=2;i<n;i++){
        int v1=abs(a[pre]-a[pos]);
        int v2=abs(a[nex]-a[pos]);
        if(v1>v2)
            res+=v2,pos=nex++;
        else
            res+=v1,pos=pre--;
    }
    printf("%lld\n",res);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 686ms, 内存消耗: 4216K, 提交时间: 2019-12-08 17:49:31

#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 1e6 + 10 ;
int a[N] ;  
int main(){
	int n , m ; 
	cin >> n >> m ;
	for (int i = 0 ; i < n ; ++ i)
		cin >> a[i] ;
	sort(a,a+n) ;
	int i = n-1 ; 
    while(i >= 0 && a[i] > m)   -- i ; 
	int l = i , r = i+1 ;
	long long sum = 0 ;  
	while(l >= 0 || r < n){
		if ((l >= 0 && m-a[l] <= a[r]-m) || r == n){
			sum += m-a[l] ; 
			m = a[l] , -- l ;
		}
		else{
			sum += a[r]-m ;
			m = a[r] , ++ r ;
		}
	} 
	cout << sum << endl ; 
	return 0 ;
}

详情