当前位置：首页 > news >正文

寻找最优美做题曲线

news 来源：原创 2025/7/15 8:47:03

题目描述

一个有趣的评测功能，就是系统自动绘制出用户的“做题曲线”。所谓做题曲线就是一条曲线，或者说是折线，是这样定义的：假设某用户在第 bi 天 AC 了 ci 道题，并且 bi 严格递增，那么该用户的做题曲线就是平面上点 (i,ci) 依次连出的一条折线。比如你在第 1 天做了 3 道题，第 3 天做了 4 道题，第 6 天做了 1 道题，那么你在前 6 天的做题曲线就是从点 (1,3) 到点 (2,4) 到点 (3,1) 的连续折线。

nodgd 同学可以预测出自己未来 N 天每条能够 AC 题目的数量，同时有一个很无趣的爱好，就是单调递增，nodgd 强迫自己的做题曲线保持严格的单调递增。但是出于某些原因，nodgd 在某些日子（共有 K 天）必须刷题，而且刷题数量一定是预计的数量（体现 nodgd 的神预测）。nodgd 同学想知道，在这样的情况下，自己最多有多少天可以刷题，不过 nodgd 同学还有大量的数学竞赛题、物理竞赛题、英语竞赛题、美术竞赛题、体育竞赛题……要做，就拜托你来帮他算算了。

输入格式

第一行两个正整数，N 和 K，表示 nodgd 预测了未来 N 天每天做题的数量，其中 K 天必须刷题。

第二行 K 个正整数 pi，表示第 pi 天必须刷题 (1≤pi≤N，保证每个 pi 不同）。

第三行 N 个正整数 ci，表示在第 i 天 nodgd 可以 AC 的题目数量必须是 ci。

输出格式

输出共一行。

如果能找到严格递增的做题曲线：一个正整数，表示 nodgd 最多有多少天可以刷题。

如果找不到严格递增的做题曲线：直接输出 impossible（不加引号，全是小写字母）。

输入输出样例

输入 #1复制

13 4
2 13 8 7
6 10 9 8 9 10 11 16 14 12 13 14 18

输出 #1复制

说明/提示

数据范围及约定

对于全部数据，

1≤N≤500000，1≤K≤N/2；
1≤p[i]≤N，保证每个 p[i] 不同，不保证 p[i] 按大小顺序输入；
1≤c[i]≤109。

无限制求法

要想知道怎么求有限制的首先还是得知道怎么求没有限制的。

第一种方法是动态规划，由于没啥用直接省去。如果有需要可以百度。复杂度为平方级别。

第二种方法也就是用的最多的方法，贪心+二分。

算法流程：

从头开始遍历每一个原来的元素，然后在最长子序列数组中，将大于等于这个遍历到的元素的第一个元素的位置直接改为这个元素。（有一点绕）

例如目前有一个上升子序列 2 3 6 9，

然后我扫描到了一个7，

于是我找到上升子序列中的9将它改成7。

特别的，如果没有大于等于它的元素，便直接将它插入到上升子序列的末尾。

最后我们得到的上升子序列就是最长的了。

强行解释：

贪心原理：对于一个上升子序列，在长度相同的情况下，其末尾的元素越小，越有利于接下来的增长。

例如，序列2 3 5是比序列2 3 9更优的（想象这三个元素后面还有一个元素7）。

正确性显然

为了简化代码，我们不需要判断当前元素是否可以放到上升子序列的末尾，每一次直接替换掉大于等于它的第一个元素。等于可以排除两个相等的元素的影响，避免序列中出现两个相同的元素使答案错误。

正确性依然显然

找大于等于他的第一个元素直接用二分查找即可。

我们讨论以下这个序列：

1 5 3 7 4 6

显然他的最长上升子序列是1 3 4 6

首先找到第一个元素1，由于现在上升子序列中没有元素（相当于没有大于等于它的），直接插入。然后上升子序列变为1。

接着找到第二个元素5，也没有大于等于它的，直接插入。上升子序列变为 1 5。

接着找到第三个元素3，根据贪心原理，找到第一个大于等于它的元素5，将5改为3。上升子序列变为1 3。

然后找到第四个元素7，插入最后。上升子序列变为1 3 7。

然后找到第五个元素4，通过上述方法把7改成4。上升子序列变为1 3 4。

最后找到第六个元素6，插入最后。上升子序列变为1 3 4 6。

至此，算法完美结束。

有没有体会到一点？

有限制后的求法

由于有一些元素是必须选择的，我们的算法需要有所调整。

首先我们通过一张图直观的看看在两个必须选择的元素中间有哪些是显然不会被选择的。

图中橙色的1 2 4号都是不可能被选择的。

因为1号和二号比必选1更小，要求序列严格上升，因此不可能出现在最终答案里面。但是由于上面的算法会用它们去替换上升子序列中更大的元素甚至是必选的元素，因此遍历它们会导致答案的错误。

而4号比必选2更大，如果要选择必选2元素，4号不可能出现在最终答案里面。同样的，如果用上面的算法会把他们直接插入上升子序列的最后，直接导致答案的错误。

他们对答案没有贡献，且会导致最终答案计算错误。

而3号和5号的大小介于两个必选之间，都是可能被选择的。

根据上述分析，我们只需要删去两个必选之间比前一个必选更小的和比后一个必选更大的所有数（打一个标记就行），然后跑一遍之前说的没有限制的算法就可以得到最后的答案了。由于输入必选的元素编号不保证有序，我们需要排一次序。

无解的情况当且仅当必选的子序列不是单调上升的。（显然）

在打代码的时候需要注意细节，第一个必选之前和最后一个必选之后的区间也需要考虑。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,a[1000001],p[1000001],cnt,t[1000001];
bool b[1000001];
int main()
{cin>>n>>k;for(int i=1;i<=k;i++)scanf("%d",&p[i]);//读入必选的元素，排序。 sort(p+1,p+k+1);for(int i=1;i<=n;i++)scanf("%d",&a[i]);	for(int i=1;i<=k;i++)//无解的情况当且仅当必选的子序列不是单调上升的{if(a[p[i]]<=a[p[i-1]]){cout<<"impossible"<<endl;return 0;}}p[k+1]=n+1;a[n+1]=1e9+5;//第一个必选之前和最后一个必选之后的区间也需要考虑for(int i=1;i<=n;i++)//删去对答案没有贡献且会导致答案出现错误的元素 {if(p[cnt+1]==i){cnt++;continue;}if(a[i]<=a[p[cnt]]||a[i]>=a[p[cnt+1]])b[i]=1;}cnt=0;//反复利用for(int i=1;i<=n;i++){if(b[i])continue;//跳过标记的元素 if(a[i]>t[cnt])//正常的最长上升子序列算法 {t[++cnt]=a[i];}else{int x=lower_bound(t+1,t+cnt+1,a[i])-t;//正常的二分 t[x]=a[i];}}cout<<cnt<<endl;//正常的输出return 0;//非同寻常的退出程序 
}