xtu oj 删除

🕗 发布于 2024-11-11 05:46 c

文章目录

回顾
代码
思路
总结

回顾

代码

#include<stdio.h>
#include<stdbool.h>
#define N 100010
int a[N],n,k,jjj[N],ttt[N],pos1,pos2;//故意写在一行的，让代码行数少一点，a 数组存数字,jjj 和 ttt 都是存 a 里面的数字
//pos1 和 pos2 都是标记下标的位置的，下次不这么定义了，变量全写在一行看起来不是很方便
void sort(int q[],int l,int r){//快速排序模板
if(l>=r){
return;
}
int i=l-1,j=r+1,x=q[(l+r)/2];
while(i<j){
do{
i++;
}while(q[i]<x);
do{
j--;
}while(q[j]>x);
if(i<j){
int temp=q[i];
q[i]=q[j];
q[j]=temp;
}
}
sort(q,l,j);
sort(q,j+1,r);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}//输入
sort(a,1,n);//排序
for(int i=1;i<=n;i++){
jjj[i]=a[i];
ttt[i]=a[i];
}
for(int i=2;i<=n;i++){//从左边往右边按照题意处理，
if(jjj[i]-jjj[i-1]<=k){
jjj[i]=(jjj[i]+jjj[i-1])/2;
}else{
pos1=i;//pos1-1 这个位置的元素前面的所有元素都是可以删除的
break;
}
if(i==n){
pos1=n+1;
}
}
for(int i=n-1;i>=1;i--){//从右边往左边处理
if(ttt[i+1]-ttt[i]<=k){
ttt[i]=(ttt[i+1]+ttt[i])/2;
}else{
pos2=i;//pos2+1 右边的所有元素都是可以删除的 
break;
}
if(pos2==1){
pos2=0;
}
}
bool flag=false;//哨兵，起到一个标记的作用
for(int i=pos2+1;i<pos1;i++){//看区间交界的地方能不能删除，啥意思呢，就是pos-1 左边的是所有元素都可以删除
if(ttt[i]-jjj[i-1]<=k){//pos2+1 右边的所有元素都可以删除，有点像双指针了。两个区间交集的部分能满足条件 
printf("Yes\n");//那就可以删除到最后只剩下一个元素
flag=true;
break;
}
}
if(!flag){
printf("No\n");
}
return 0;
}

思路

再写一个算法题就去复习 SOA 。

题目的意思感觉就是问能不能通过贪心操作，每一次选择最优的策略，使得原来的数组元素尽可能地减少，最后只剩下一个元素，假设可以就输出 Yes

数组的大小是 10^5 ，感觉很多题的数组都是这个大小。这个时间复杂度的话，感觉线性时间复杂度，或者 O(nlogn) 都可以。感觉排序，二分，双指针都可以考虑（指的是这个时间复杂度，不是指这个题）

这个题排序应该是一定要用的，之前看 codeforces 的讲解视频，那个博主说他一般拿到一个数字数组就先排个序再说。应该是要去判断最大的数字和最小数字的和除以 2 ，向下取整和 k 去比较。假设大于 k 的话，是不是就不行了呢？

我们要考虑的是，向下取整会把小数部分去掉，这个特性可以把原来的数字减小一点，那么能产生什么影响呢？感觉前面的想法没啥问题，我试试看。

应该意思是，极限情况就是 k 比较小，很接近所有数字的平均数，假设这个平均数严格大于 k ，应该就是要输出 No ，不知道我有没有理解错意思。假设要求所有数字的和的话，还要用 long long 才行。

直接超时了，嗷嗷，我知道了，冒泡排序是 n^2 的时间复杂度，不超时都没有天理了，所以我记着冒泡排序的意义是什么呢，还记不住。

#include<stdio.h>
#include<stdbool.h>
#define N 100010
#define LL long long
int a[N],n,k;//故意写在一行的，让代码行数少一点
void bubble_sort(int a[],int n){//冒泡排序差点又忘记怎么写了
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-i;j++){
if(a[j]>a[j+1]){
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
int main(){
scanf("%d%d",&n,&k);
LL sum=0;//求数组所有数字的和
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];//求和
}
bubble_sort(a,n);//排序
if(sum/n>k){//平均数大于 k ，一定不行
printf("No\n");
}else{
bool have_ans=false;//标记，看有没有输出答案，这种专业一点是不是叫作哨兵呀
for(int i=0,j=n-1;i<n/2&&j>=0;i++,j--){//双指针，看最大的数字和最小的数字的平均数和 k 的大小关系
if((a[i]+a[j])/2>k){
printf("No\n");
have_ans=true;//标记为输出了答案
break;
}
}
if(!have_ans){//没输出答案的话就输出一个答案
printf("Yes\n");
}
}
return 0;
}

写一个快速排序，应该是 O(nlogn) 的时间复杂度，应该就可以了。换成快排之后还是不行呀，只能过 75 的数据点，是有啥情况没有考虑到吗？

#include<stdio.h>
#include<stdbool.h>
#define N 100010
#define LL long long
int a[N],n,k;//故意写在一行的，让代码行数少一点
void sort(int q[],int l,int r){//快速排序模板
if(l>=r){
return;
}
int i=l-1,j=r+1,x=q[(l+r)/2];
while(i<j){
do{
i++;
}while(q[i]<x);
do{
j--;
}while(q[j]>x);
if(i<j){
int temp=q[i];
q[i]=q[j];
q[j]=temp;
}
}
sort(q,l,j);
sort(q,j+1,r);
}
int main(){
scanf("%d%d",&n,&k);
LL sum=0;//求数组所有数字的和
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];//求和
}
sort(a,0,n-1);//排序
if(sum/n>k){//平均数大于 k ，一定不行
printf("No\n");
}else{
bool have_ans=false;//标记，看有没有输出答案，这种专业一点是不是叫作哨兵呀
for(int i=0,j=n-1;i<n/2&&j>=0;i++,j--){//双指针，看最大的数字和最小的数字的平均数和 k 的大小关系
if((a[i]+a[j])/2>k){
printf("No\n");
have_ans=true;//标记为输出了答案
break;
}
}
if(!have_ans){//没输出答案的话就输出一个答案
printf("Yes\n");
}
}
return 0;
}

或者说，我直接完整遍历一遍，好像也可以，线性时间复杂度，完全可以接受，也不存在遗漏的情况。哭了，只能过 69 的数据点，应该是我思路逻辑上哪里出了问题。

#include<stdio.h>
#include<stdbool.h>
#define N 100010
#define LL long long
int a[N],n,k;//故意写在一行的，让代码行数少一点
void sort(int q[],int l,int r){//快速排序模板
if(l>=r){
return;
}
int i=l-1,j=r+1,x=q[(l+r)/2];
while(i<j){
do{
i++;
}while(q[i]<x);
do{
j--;
}while(q[j]>x);
if(i<j){
int temp=q[i];
q[i]=q[j];
q[j]=temp;
}
}
sort(q,l,j);
sort(q,j+1,r);
}
int main(){
scanf("%d%d",&n,&k);
LL sum=0;//求数组所有数字的和
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];//求和
}
sort(a,0,n-1);//排序
if(sum/n>k){//平均数大于 k ，一定不行
printf("No\n");
}else{
bool have_ans=false;//标记，看有没有输出答案，这种专业一点是不是叫作哨兵呀
for(int i=0;i<n-1;i++){
if((a[i]+a[i+1])/2>k){
printf("No\n");
have_ans=true;//标记为输出了答案
break;
}else{
a[i+1]=(a[i]+a[+1])/2;
}
}
if(!have_ans){//没输出答案的话就输出一个答案
printf("Yes\n");
}
}
return 0;
}

是不是要考虑那种不能整除的优先，对对，这才符合贪心策略，因为刚好整除的话对总和就没有数字损失，假设不能刚好整除的话，向下取整就会让所有数字的综合减小。应该是这样。

不能整除的情况就是两个元素，一个是奇数，一个是偶数的时候，所以是不是把原来输入的时候就存到两个不同的数组里面呢？这个时候又有一个问题，就是假设我们把奇数和偶数求平均数之后把答案存到哪儿呢，我们需要不断地操作，直到只剩下一个元素，但是，这样子的时间复杂度是不是可以接受的，还有这样子要怎么实现。

现在最大的问题就是怎么让奇数和偶数求和。新产生的奇数和偶数要怎么继续循环下去。或者说，我们只需要判断最后存不存在，是不是不用事实上实现，只需要写一个条件表达式判断一下，那这个表达式怎么写。是不是还是和前面一样，判断一下最大的和最小的数字的平均数，就可以了呢。

举一个例子可以直观理解前面说的贪心策略：假设输入的是 1 2 3 4 5 6 7 8 ，那么奇数是 1 3 5 7 ，偶数是 2 4 6 8 ，我们让奇数加偶数，按题意操作，最后剩下的一个数字是 5 ，让相同奇偶性的数字相加，最后剩下的数字是 4 ，这和我想的结论好像矛盾了，有点奇怪。奥也不是，没矛盾，感觉肯定是要奇数和偶数相加，判断一下奇数和偶数求平均数能不能行，不行的话，相同奇偶性肯定更加不行。

那是不是就是双指针判断最大的元素和最小的元素的平均数，两个元素假设相同奇偶性就换到不同奇偶性的元素，我试试看。

等一下，我突然发现自己审题错了。。。这个不是两个数的平均数小于 k ，是两个数的差的绝对值小于 k ，那这样的贪心策略应该就是每次选最接近的两个数字。所以前面能通过一些测试点完全就是运气。

下面说一下能过的代码的思路是啥，前面是自己的做题过程。我们可以看到有一个绝对值，那么我们要么就是用 abs 函数，要么就是用大的数字减去小的数字，假设现在给定一个元素，是一个比较一般的元素，该元素左边和右边都有元素，那么它是不是要选择一个最接近自己的元素去消除，有 10^5 个元素，假设都这么直观地去选择应该是不行的，应该是要按照一定的顺序去选择。

这里首先把数组从小到大排序，用大的数字减去小的数字，就可以删除掉一个元素，然后更新一个元素，那可以把原来的数组的所有元素存到两个数组里面，这里把这两个数组叫做 jjj 和 ttt

我们从左边往右边按照题意处理 jjj 里面的所有元素，直到不能满足题目要求或者遍历完整个 jjj 数组，我们把结束的位置的下标记为 pos1 ，注意，pos1-1 对应的元素还没有被删除，pos1-1 左边的所有元素都被删除了（也不是真的删除了，就是按照题意是能被删除的元素）

从右边往左边按照题意处理 ttt 里面的所有元素。结束的位置记为 pos2 ，注意 pos2+1 对应的元素没有被删除，pos2+1 右边的所有元素理论上都可以被删除。

然后经过上面的处理，有两个区间的元素，理论上是可以被删除的，[1,pos1-2] 和 [pos2+2,n] ，然后我们就处理两个区间的交集，假设这个交集的元素，有能满足条件的，那么整个区间 [1,n] 就变成了理论上可以删除到只剩下一个元素的情况。

好像 c 语言也有快排函数，不用自己写一个。搜了一下，但是需要自己额外写一个 cmp 函数，感觉比较复杂，不如记一下快排模板哈哈。

总结

前面不知道有没有讲清楚，这里再简短说一下。就是从左往右处理一遍，然后从右往左处理一遍，最后看两个区间的交集能不能满足条件，做一个判断即可，这种感觉就是积累一下这个做法，考试的时候要是遇上这个题就比较幸运，以前笔者程设考试的时候就遇到过一个平时练习的题目。

原文地址：https://blog.csdn.net/L3102250566/article/details/143657263

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：C#里对数组的排序操作
下一篇：Hadoop学习--第一章 Hello大数据分布式

C#调试项目_附加进程调试
c#项目附加进程一级目录二级目录三级目录一级目录二级目录三级目录
阅读更多2024-11-15
线程-2-线程概念与控制
线程概念与控制，局部性原理， POXIS接口，分页式存储结构，页表结构，缺页中断
阅读更多2024-11-15
洛谷 P4011 孤岛营救问题（BFS分层图最短路，状态压缩）
我们考虑对已获得的钥匙进行二进制状态压缩。注意：同一个格子可能有多把钥匙，一开始的。显然，我们直接使用BFS求最短路即可。这个格子，且当前已有钥匙的状态为。
阅读更多2024-11-15
聊天服务器(3)muduo网络库
muduo只能装在linux中，依赖boost库客户端并不需要高并发。
阅读更多2024-11-15
Unity学习---IL2CPP打包时可能遇到的问题
在这种情况下一般我们把Managed Stripping Level设置为High，然后看一下报错的提示，往link.wxl文件中添加要保留的东西即可。IL2CPP打包后会自动对Unity工程的dll
阅读更多2024-11-15
OpenGL C++视频中添加图片及文字水印播放并录制
根据前置储备，该功能的实现流程：创建一个GLThread的OpenGL运行环境；YUV数据绘制到OpenGL纹理中；图片纹理创建绘制到glViewport；文字渲染绘制到glViewport；录制视频
阅读更多2024-11-15
java实现中小企业的erp系统
java实现中小企业的erp系统
阅读更多2024-11-15
智能零售柜商品识别
本项目在智能零售商品识别的背景下，采用了多项技术创新和优化，旨在提高商品检测与识别的效率和准确性。首先，使用了PaddleX作为训练框架，这是一个高效、灵活的深度学习平台，简化了模型训练和部署的复杂性
阅读更多2024-11-15
H.265流媒体播放器EasyPlayer.js网页直播/点播播放器WebGL: CONTEXT_LOST_WEBGL错误引发的原因
EasyPlayer.js播放器不仅支持H.264与H.265视频编码格式，还具备直播、点播、录像、快照截图、MP4播放、多屏播放、倍数播放、全屏播放等功能特性，兼容Windows、Linux、And
阅读更多2024-11-15
ubuntu连接orangepi-zero-2w桌面的几种方法
线连接 Orange Pi 开发板和 HDMI 显示器。然后打开 Nomachine 图形化连接开发板。例如使用finalshell 连接开发板。其中视频采集卡是usb输出，hdmi输入。线 +
阅读更多2024-11-15

xtu oj 删除

文章目录

回顾

代码

思路

总结

相关文章