简答题 偏难
#19998

金币收集

金币收集

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;algorithm&gt; #include &lt;cstdio&gt; using namespace std; const int INF = 2e9; const int N = 100005; int n; int x[N], t[N]; int p[N], f[N]; int mx; // 排序规则:先按x升序,x相同则按t升序 bool cmp(int a, int b) {     if (x[a] != x[b])         return x[a] &lt; x[b];     return t[a] &lt; t[b]; } int main() {     scanf("%d", &amp;n);     for (int i = 1; i &lt;= n; ++i) {         scanf("%d%d", &amp;x[i], &amp;t[i]);         t[i] -= x[i];  // 转换为 t' = t - x         p[i] = i;      // 下标数组,用于排序         f[i] = INF;     }     // 按x从小到大排序所有点     sort(p + 1, p + n + 1, cmp);          mx = 0;     f[0] = 0;     for (int i = 1; i &lt;= n; ++i) {         int val = t[p[i]];         if (val &lt; 0) continue; // 负数直接无法选取                  // 二分查找最大长度r,满足 f[r] &lt;= val         int l = 0, r = mx;         while (l &lt; r) {             int mid = (l + r) / 2 + 1;             if (val &lt; f[mid])                 r = mid - 1;             else                 l = mid;         }         // 可以拼出长度 r+1 的子序列         mx = max(mx, r + 1);         if (val &lt; f[r + 1]) {             f[r + 1] = val;         }     }     printf("%d\n", mx);     return 0; }</pre>
这道题暂未补解析。