链接

题意: 在一条数轴上有m个障碍，将数轴分成若干份，障碍可能位于端点。记x为移除的障碍，L为该区间内最长的线段。怎么使L - x * x最大。

题解： 枚举移除一个障碍到移除m个障碍的情况。因为 L - x * x 要最大。而L < x * x 时为负数，故x的范围为sqrt(L)，由题意知L的范围了2e5，所以只需要枚举到移除500个障碍即可。

代码



#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#define PI 3.14159
using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 3e5+15;
const int mod = 1e9+7;

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int> alls;
    for(int i=0;i<m;i++)
    {
        int t;
        cin>>t;
        if(t!=0 && t!=n)
            alls.push_back(t);
    }
    alls.push_back(0);
    alls.push_back(n);
    sort(alls.begin(),alls.end());
    
    int res = 0;
    for(int i=1;i<=500;i++)
    {
        for(int j=i+1;j<alls.size();j++)//枚举右端点
        {
            res = max(res,(alls[j]-alls[j-1-i])-i*i);
        }
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int T = 1;
    while(T--)
    {
        solve();
    }
}