前言:这一题似乎用不了二分以及三分,害我写这么久,但是查找下一个元素的时候要用到二分查找
题目地址
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"int n;
const int N = (int)2e5+10;
vector<int> a;
int ans = 0x3f3f3f3f;int check(int x){int cnt = x;int pos = a[1];while (1) {cnt++;pos = std::upper_bound(a.begin() + 1, a.end(), pos + x) - a.begin();if (pos == a.end() - a.begin()) break;pos = a[pos];}ans = min(ans,cnt);return cnt;
}int main(){cin >> n;a.push_back(0);for(int i=1;i<=n;i++){int x; cin >> x;a.push_back(x);}//a.push_back(0x3f3f3f3f);sort(a.begin()+1,a.end());for(int i=0;i<=600;i++) check(i);cout << ans;system("pause");return 0;
}