A. 比赛提案[CF1972A]

    传统题 1000ms 256MiB

比赛提案[CF1972A]

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

[题意]

一场竞赛包含$n$道题,第$i$道题的难度最多为$b_i$,第$i$个问题的难度为$a_i$。

最初$a_1, a_2,...a_n$都是按递减顺序排序的。
$a$中有些问题可能会要比预期的更难,为了使得最终$a_i \le b_i$,所以要提出更多的问题。

每当提出一个难度为$w$的新问题,最难的问题需要被删除,并以非递减顺序的方式对问题进行排序。
换句话说,在每个操作中,选择一个整数$w$,将其插入到数组$a$中, 并按非递减顺序对数组$a$进行排序,最后删除其中的最后一个元素(最大的元素)。
为所有的问题找出需要生成新问题的最小数量,使得$a_i \le b_i$。

输入一个$T (1 \le T \le 100)$,是样例的组数。
接下来一个整数$n (1 \le n \le 100)$。
然后是$n$个整数,输入$a$数组$(1 \le a_1 \le a_2 \le ⋯ \le a_n \le 10^9)$。
然后是$n$个整数,输入$b$数组$(1 \le b_1 \le b_2 \le ⋯ \le b_n \le 10^9)$。


[样例输入]

2
6
1000 1400 2000 2000 2200 2700
800 1200 1500 1800 2200 3000
6
4 5 6 7 8 9
1 2 3 4 5 6

[样例输出]

2
3

[提示]

在第一个样例中:
加入一个$w=800$的新问题,则$a$为$[800,1000,1400,2000,2000,2200]$。
加入一个$w=1800$的新问题,则$a$为$[800,1000,1400,1800,2000,2000]$。
可以证明没有更优的解法。

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N], b[N];
int main(){
    //使用双指针,统计a[t1]比b[t2]大的次数
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        for(int i=1; i<=n; i++) scanf("%d", &b[i]);
        int t1=1, t2=1, ans=0; b[n+1]=1e9+10; //初始化,设好边界
        while(t1<=n-ans){
            while(a[t1]>b[t2]) ans++, t2++; //a[t1]比b[t2]大,t2往后移
            t1++; t2++; //都往后移
        }
        printf("%d\n", ans);
    }
    return 0;
}

提高测试:div2难度(时间3.5h)

未参加
状态
已结束
规则
XCPC
题目
7
开始于
2024-8-23 8:30
结束于
2024-8-23 12:00
持续时间
3.5 小时
主持人
参赛人数
11