通过海量题库、编程比赛和实时排名,系统化提升您的编程能力。
"NOIP真题" 试卷中 NOIP第十六届全国青少年信息学奥林匹克联赛初赛试题[2010提高组] 中有题目如下:
第1题
(烽火传递) 烽火台又称烽燧,是重要的军事防御设施,一般建在险要处或交通要道上。 一旦有敌情发生,白天燃烧柴草,通过浓烟表达信息;夜晚燃烧干柴,以火光传递军情。在 某两座城市之间有 n 个烽火台,每个烽火台发出信号都有一定的代价。为了使情报准确地传 递,在连续的 m个烽火台中至少要有一个发出信号。现输入 n、m和每个烽火台发出信号的代 价,请计算总共最少花费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确传 递。
例如,有 5 个烽火台,他们发出信号的代价依次为 1,2,5,6,2,,且 m为 3,则总共最少 花费代价为 4,即由第 2 个和第 5 个烽火台发出信号。
#include<iostream> #include<cstring> using namespace std; const int SIZE=100; int n,m,r,value[SIZE],heap[SIZE], pos[SIZE],home[SIZE],opt[SIZE]; //hep[i] 表示用顺序数组储存的堆 heap 中第 i 个元素的值 //pos[i] 表示 opt[i] 在堆 heap中的位置,即 heap[pos[i]]=opt[i] //home[i] 表示 heap[i] 在序列 opt 中的位置,即 opt[home[i]]=heap[i] void swap(int i,int j)// 交换堆中的第 i 个和第 j 个元素 { int tmp; pos[home[i]]=j; pos[home[j]]=i; tmp=heap[i]; head[i]=head[j]; heap[j]=tmp; tmp=home[i]; home[i]=home[j]; home[j]=tmp; } void add(int k)// 在堆中插入 opt[k] { int i; r++; heap[r]= ① ; pos[k]=r; ② ; i=r; while( (i>1) && (heap[i]<heap[i/2]) ) { swap(i,i/2); i/=2; } } void remove(int k)// 在堆中删除 opt[k] { int i,j; i=pos[k]; swap(i,r);; r--; if(i==r+1) return ; while( (i>1)&&(heap[i]<heap[i/2]) ) { swap(i,i/2); i/=2; } while(i+i<=r) { if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) ) j=i+i+1; else ③ ; if(hea[i]>heap[j]) { ④ ; i=j; } else break; } } int main() { int i; cin>>n>>m; for(i=1;i<=n;i+++) cin>>value[i]; r=0; for(i=1;i<=m;i++) { opt[i]=value[i]; add(i); } for(i=m+1;i<=n;i++) { opt[i]= ⑤ ; remove( ⑥ ); add(i); } cout<<heap[1]<<endl; return 0; }
所属试卷:NOIP第十六届全国青少年信息学奥林匹克联赛初赛试题[2010提高组]
(读者自行创建,注意每行第一个逗号后面有空格),其内容
(本题 9 分)某公司在承建国家重大工程项目时,工程部
有以下程序程序运行后的输出结果是( )。
有以下程序:程序运行后的输出结果是( )。
C语言中的标识符分为关键字、预定义标识符和用户标识符,
内联函数执行起来比标准函数______________
编写程序,其功能为打印如下图所示图形。 * *** *
已知列表x=[1,3,2],那么执行语句 x=x.re
若在 main函数中定义,char*s ="hel
在C语言中,用关键字____________定义单精度
有以下程序,程序中库函数islower (ch)用以判
已知,计算f(n)的C语言函数f1如下:将f1中的in
前台启动的进程使用复合键______终止。
若从任一目录用什么命令可快速转到用户家目录?
从事物的特性到计算机中的数据表示,经历的三个领域是现实
存在一个等待事务集{T0,T1,„,Tn},其中T0正
在DBMS的授权子系统中,授权和回收权限的语句分别是G
若串S1=‘ABCDEFG’, S2=‘9898’ ,
在图采用邻接矩阵存储时,Prim 算法的时间复杂度为
在 TCP/IP 参考模型中TCP协议工作在
学生关系模式 S( S#,Sname,Sex,Age)
下列存储器中,汇编语言程序员可见的是( )。Ⅰ. 指令
设有以下共用体类型说明和变量定义,则变量d在内存所占字
C语言中,二维数组在内存中的存放方式为按_____优先
为了避免嵌套条件语句的二义性,C语言规定else与其前
C语言中引用数组元素的方括号可以用花括号代替。
结构化程序所要求的基本结构不包括
设有宏定义:#define IsDIV(k,n)((k
下面描述中正确的是
IT 的含义是( )。
更多选择题
更多填空题
计算机二级Python语言程序设计模拟试卷
Python第三方库
2025年考研408计算机统考真题在线评测(附答案)
Python标准库
Python函数
Python文件
Python组合数据类型