话不多说，直接上代码：

#include <bits/stdc++.h>
using namespace std;
int k[1000010],dp[100010];
int n,ans,a,b;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        k[a]=b;
    }
    for(int i=0;i<=1000000;i++)
    {
        if(k[i]){
            int j=i-k[i]-1;
            if(j>=0){
                dp[i]=dp[j]+1;
            }
            else
            {
                dp[i]=1;
            }
        }
        else{
            dp[i]=dp[i-1];
        }
        ans=max(ans,dp[i]);
    }
    cout<<n-ans;
    return 0;
}

打码不易，点个赞吧！

100 Accepted

f[i]表示从i开始从右往左激活激光塔，最终摧毁的激光塔数量。初始状态f[0]=0。可以使用二分找到没有激活i之后，被摧毁的最左边的激光塔p，那么状态可以转移为f[p - 1] + i - p（其中i-p是被i摧毁的激光塔数量）。枚举添加新激光塔后，没有被摧毁的最右边的激光塔i，则被摧毁的激光塔数量为f[i] + n - i，取最小值即为答案。

sort(t + 1, t + n + 1);
for (int i = 1; i <= n; i++) {
	int p = lower_bound(t + 1, t + i, (T){t[i].a - t[i].b, 0}) - t;
	f[i] = f[p - 1] + i - p;
}
int ans = 1e9;
for (int i = 1; i <= n; i++)
	ans = min(ans, f[i] + n - i);
cout << ans << endl;

struct T {
    int a, b;
    bool operator < (const T& x) const {
        if (a == x.a)
            return b < x.b;
        return a < x.a;
    }
} t[MAXN];

😄

#include <bits/stdc++.h> using namespace std; int k[1000010], dp[1000010]; int n, a, b, ans; int main() { cin >> n; for (int i = 0; i <n ; i ++) { cin >> a >> b; k[a] = b; } for (int i = 0; i <= 1000000; i ++) { if (k[i] > 0) { int pre = i - k[i] - 1; if (pre >= 0) { dp[i] = dp[pre] + 1; } else dp[i] = 1; } else { dp[i] = dp[i - 1]; } ans = max(ans, dp[i]); } cout << n - ans; }

#include <bits/stdc++.h> using namespace std; int k[1000010],dp[100010]; int n,ans,a,b; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a>>b; k[a]=b; } for(int i=0;i<=1000000;i++) { if(k[i]){ int j=i-k[i]-1; if(j>=0){ dp[i]=dp[j]+1; } else { dp[i]=1; } } else{ dp[i]=dp[i-1]; } ans=max(ans,dp[i]); } cout<<n-ans; return 0; }