题解 | #障碍#

链接
D 障碍
思想
优美的暴力，利用x的数据范围有上限暴力求解。
代码

#include<bits/stdc++.h>
using namespace std;
const int N  = 100010;
int a[N];
void solve()
{//思想：优美的暴力
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=m;i++)cin>>a[i];
    sort(a+1,a+1+m);
    a[0] = 0,a[m+1] = n;
    int x = (int)sqrt(n), ans = -1;
    for(int i = x; i >= 0; i --)
    {//L-x*x>=0，因此x<=sqrt(L)<448
        for(int j = 0;j<=m+1-i;j++)
        {//每次拆的板子保证是连续的，保证最大值递增
            ans = max(ans,a[j+i+1]-a[j]-i*i);
        }//连续拆x个板子，遍历所有拆的可能种类数
    }
    cout << ans << endl;
}
int main()
{
    solve();
    return 0;
}