做网站六安,绵阳市建设工程质量监督站网站,生活服务信息类网站建设,水淼软件wordpress怎么设置T1:P1678 烦恼的高考志愿
评测记录:https://www.luogu.org/record/show?rid9644174 大意
有m个分数线#xff0c;有n个估分#xff0c;给每个估分找一个最接近的分数线#xff0c;输出每个估分和它最接近的分数线的差之和。 解题思路
我们先将分数排序 我们可以找到一个…T1:P1678 烦恼的高考志愿
评测记录:https://www.luogu.org/record/show?rid9644174 大意
有m个分数线有n个估分给每个估分找一个最接近的分数线输出每个估分和它最接近的分数线的差之和。 解题思路
我们先将分数排序 我们可以找到一个估分的分数线前驱那么这个的后一个就是这个估分的分数线后继那么我们将估分和这两个的差取最小值就是最接近的分数线。然后第一个和最后一个特殊处理一下就好了。 code
#includecstdio
#includealgorithm
using namespace std;
int n,m,a[100001],f,l,r,mid,ans;
int finds(int x)//查找前驱
{int l1,rn,mid;while (lr){mid(lr1)/2;if (a[mid]f) lmid;else rmid-1;}return l;
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)scanf(%d,a[i]);sort(a1,a1n);for (int i1;im;i){scanf(%d,f);int fdfinds(f);if (fd1fa[fd]||fdn) ansabs(f-a[fd]);//特判else ansmin(f-a[fd],a[fd1]-f);//取最小}printf(%d,ans);
} T2:P3902 递增
评测记录https://www.luogu.org/recordnew/lists?uid52918pidP3902 大意
一个长度为nnn的序列a" role="presentation">aaa求至少修改多少个数可以使这个序列变成最长上升子序列。 解题思路
我们可以先求出这个序列的最长上升子序列然后修改不在这个序列内的数就好了那么答案就是n−LISnumn−LISnumn-LIS_{num} code
#includecstdio
using namespace std;
int n,a[100001],tail,h[100001];
int finds(int x)//查找前驱
{int l1,rtail,mid;while (lr){mid(lr)/2;if (h[mid]x) lmid1;else rmid;}return l;
}
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d,a[i]);tail0;for (int i1;in;i){if (a[i]h[tail]) h[tail]a[i];//加入序列else h[finds(a[i])]a[i];//修改序列}printf(%d,n-tail);//输出答案
}
