2812: 【算法思想】【双指针】最小差

题目描述

给定N个整数A1， A2， … ，AN，以及一个正整数K。问在所有两个数的差Ai-Aj中大于等于K的最小的差是多少(其中Ai>Aj而且i!=j,N<=100000)

输入

第一行输入n和k

第二行输入n个整数

输出

所有两个数的差(Ai-Aj)中大于等于K的最小的差,若不存在最小差则输出“no answer!”

样例输入

6 3
3 1 8 7 15 10

样例输出

3

Code:

#include<bits/stdc++.h>
using namespace std;
int n,k,minx,a[100005]; 
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    if(a[n-1]-a[0]<k){
        cout<<"no answer!";
        exit(0);
    }
    minx=a[n-1]-a[0];
    int j=0;
    for(int i=0;i<n;i++){
        while(j<=n-1&&a[j]-a[i]<k){
            j++;
        }
        if(a[j]-a[i]>=k&&a[j]-a[i]<minx){
            minx=a[j]-a[i];
        }
    }
    cout<<minx<<endl;
    return 0;
}
/**************************************************************
    Problem: 2812
    User: yangrenrui
    Language: C++
    Result: 正确
    Time:123 ms
    Memory:2572 kb
****************************************************************/