首先问题满足单调性，所以可以二分答案，设二分出的答案为h
这题n<=2000可以用dp做
设dp[i]为第i个数字不修改时满足答案h最少要修改的次数
枚举上一次不修改的位置j
那么j+1~i-1的位置的数都是要修改的
一个显然的结论是，这n个数应该修改得使其均匀的分布在a[i]~a[j]之间，这样相邻差的最大值最小，为abs(a[i]-a[j])/i-j 上取整
所以如果算完在h之内，dp[i]=min(dp[i],dp[j]+i-j-1)
最后ans=min(dp[i]+n-i)
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdlib> #include <utility> #include <map> #include <stack> #include <set> #include <vector> #include <queue> #include <deque> #define x first #define y second #define mp make_pair #define pb push_back #define LL long long #define Pair pair<int,int> #define LOWBIT(x) x & (-x) using namespace std; const int INF=2e9; int n,k; int a[2048]; int dp[2048]; inline int myabs(int x) { return x>=0?x:-x; } bool check(int d) { int i,j; for (i=0;i<=n;i++) dp[i]=INF; dp[0]=dp[1]=0; for (i=2;i<=n;i++) { dp[i]=i-1; for (j=1;j<=i-1;j++) if ((myabs(a[i]-a[j])+i-j-1)/(i-j)<=d) dp[i]=min(dp[i],dp[j]+i-j-1); } int res=dp[n]; for (i=1;i<=n-1;i++) res=min(res,dp[i]+(n-i)); if (res<=k) return true; else return false; } int main () { int i; scanf("%d%d",&n,&k); for (i=1;i<=n;i++) scanf("%d",&a[i]); LL l=0,r=2e9,mid,ans; while (l<=r) { mid=(l+r)>>1; if (check(int(mid))) { ans=mid; r=mid-1; } else { l=mid+1; } } printf("%I64d\n",ans); return 0; } 这样的复杂度是O(n*n*logn)出一个加强版的数据：n<=2e5
于是有一种数学算法：
对于i<j，若满足下列条件之一，则这两个数在均不修改的情况下必定不能共存：
aj-ai>h*(j-i) , aj>ai
aj-ai<h*(i-j) , aj<ai
那么改一下不等号方向，整理得：若同时满足下面两个条件，则这两个数可以在均不修改的情况下共存
h*i-ai<=h*j-aj
h*i+ai<=h*j+aj
那我们对于每一个ai将h*i-ai和h*i+ai做成pair排个序，这样保证第一维从小到大，那么对于pair数组中的第二个数，它只要比前面的都大，就可以与前面的所有数共存
想到用一个multiset来存储这些second，然后用upper_bound(注意不能用lower_bound，因为是小于等于)来查询有没有比他大的
如果没有，全部共存，压入multiset
如果有冲突，考虑到multiset里的元素越小，越可能使后面的元素不冲突，所以可以贪心的将某个比他大的值修改成当前值
这样的做法复杂度O(n*logn*logn)
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdlib> #include <utility> #include <map> #include <stack> #include <set> #include <vector> #include <queue> #include <deque> #define x first #define y second #define mp make_pair #define pb push_back #define LL long long #define Pair pair<LL,LL> #define LOWBIT(x) x & (-x) using namespace std; int n,k; LL a[200048]; Pair has[200048]; multiset<LL> s; vector<int> seq; bool check(LL h) { int i; for (i=1;i<=n;i++) has[i]=mp(h*i-a[i],h*i+a[i]); sort(has+1,has+n+1); s.clear(); multiset<LL>::iterator pos; for (i=1;i<=n;i++) { pos=s.upper_bound(has[i].y); if (pos==s.end()) { s.insert(has[i].y); } else { s.erase(pos); s.insert(has[i].y); } } if (s.size()>=n-k) return true; else return false; } int main () { int i; scanf("%d%d",&n,&k); for (i=1;i<=n;i++) scanf("%I64d",&a[i]); LL l=0,r=2e9,mid,ans; while (l<=r) { mid=(l+r)>>1; if (check(mid)) { ans=mid; r=mid-1; } else { l=mid+1; } } printf("%I64d\n",ans); return 0; }