【贪心】 导弹拦截
【题目描述】
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：
虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。
所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。
计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。
【输入】
n颗依次飞来的高度（1≤n≤1000）。
【输出】
要拦截所有导弹最小配备的系统数k。
【输入样例】
389 207 155 300 299 170 158 65
【输出样例】
2
【提示】
输入：导弹高度： 4 3 2
输出：导弹拦截系统k=1
【题目分析】
1.需要注意的是所有的导弹必须被拦截，不存在不能被拦截的情况
2.在第一条的基础上，需要求解出最少的拦截系统
3.题目没有输入长度， 而是直接输入导弹高度，属于不确定长度的输入
【题目数据分析】
测试数据1：
输入：589 207 155 500 299 170 158 65
输出：2
方案1：
第一套：589 207 155 65
第二套： 500 299 170 158
方案2：
第一套：589 500 299 170 158 65
第二套：207 155
方案3：
第一套：589 207 155
第二套：500 299 170 158 65
测试数据2：
输入：100 90 70 80 75 65
输出：2
方案1：
第一套：100 90 70 65
第二套： 80 75
方案2：
第一套：100 80 75 65
第二套：90 70
【过程分析】
（高度和顺序都已知）
过程1：
敌方导弹高度： 100 80 90
拦截系统的高度：100 80 | 90
过程2:
敌方导弹高度： 100 90 70 80 60 65
拦截系统的高度：
假如按照顺序选择：
则第一套：100 90 70
第二套：80 60
第三套：65
实际上：
第一套：100 90 70 65
第二套：80 60
【贪心思想】
当出现新的敌方导弹时，我方从已有的拦截系统中，选取高度最低且可以拦截该导弹的那套系统，进行拦截。
【原因分析】
现在假如要拦截一个导弹，而你有5套拦截系统，都可以拦截它，为了节省你会用哪套？
肯定是使用拦截高度最低的那套，因为剩下的两套高一点的，或许还可以拦截再后面的导弹。
如果5套里面只有2套可以拦截它，那就用2套里面拦截高度最低的那套，理由同上。
如果没有能拦截该导弹的拦截系统，则新增一套
【思路框架】
【步骤1】 设置数组于基本结构
// 1.定义数组 int daodan[100]; //导弹 int lanjie[100]; // 拦截系统 int zuobiao; //记录坐标 //2.将第一枚导弹的高度先给第一套拦截系统 int k=1; //拦截系统的数量或拦截系统的编号，初始化为1 lanjie[k]=daodan[1]; // 第一个导弹的高度给第一个系统最低拦截高度 //3.遍历所有导弹 for(int i=2; i<=n; i++) { //依次考察敌方导弹daodan[2...n]的高度。 } 【步骤2】判断当前编号为i的导弹到底能不能被现有系统拦截，不能就新增一套系统
int daodan[100]; //导弹 int lanjie[100]; // 拦截系统 int zuobiao; //2.将第一枚导弹的高度先给第一套拦截系统 int k=1; //拦截系统的数量或拦截系统的编号，初始化为1 lanjie[k]=daodan[1]; // 第一个导弹的高度给第一个系统最低拦截高度 //3.遍历所有导弹 int flag; //用flag表示导弹i有没有被当前导弹系统拦截 for(int i=2; i<=n; i++) { //依次考察敌方导弹daodan[2...n]的高度。 flag=0; // 每次重置为0，表示还没有被拦截 /* 此处是判断所有拦截系统的最低高度是否大于当前导弹i的高度 成立的话要修改flag的值 */ } if(flag==0) { //说明没有任何一个导弹拦截系统可以拦截当前导弹i k++; //增加一套，k是拦截lanjie[]的下标，k++表示下一套系统 lanjie[k]=daodan[i]; //把当前没有任何系统能拦截的导弹高度给这个新系统 } else { //表示找到过一套系统 } } 【步骤3】判断拦截情况
int daodan[100]; //导弹 int lanjie[100]; // 拦截系统 int zuobiao; //2.将第一枚导弹的高度先给第一套拦截系统 int k=1; //拦截系统的数量或拦截系统的编号，初始化为1 lanjie[k]=daodan[1]; // 第一个导弹的高度给第一个系统最低拦截高度 //3.遍历所有导弹 int flag; //用flag表示导弹i有没有被当前导弹系统拦截 for(int i=2; i<=n; i++) { //依次考察敌方导弹daodan[2...n]的高度。 flag=0; // 每次重置为0，表示还没有被拦截 for(int j=1; j<=k; j++) { //遍历所有当前的系统，寻找能拦截该导弹的系统，K是当前导弹的数量 if(lanjie[j]>=daodan[i]) { //找到了，如果当前拦截系统j的最低高度lanjie[j]比daodan[i]要高 //说明了可用，但是没有比较完剩余的拦截系统就不能说最优 //寻找最优过程 } } if(flag==0) { //说明没有任何一个导弹拦截系统可以拦截当前导弹i k++; //增加一套，k是拦截lanjie[]的下标，k++表示下一套系统 lanjie[k]=daodan[i]; //把当前没有任何系统能拦截的导弹高度给这个新系统 } else { } } 【步骤4】判断能拦截的情况
int daodan[100]; //导弹 int lanjie[100]; // 拦截系统 int zuobiao; //2.将第一枚导弹的高度先给第一套拦截系统 int k=1; //拦截系统的数量或拦截系统的编号，初始化为1 lanjie[k]=daodan[1]; // 第一个导弹的高度给第一个系统最低拦截高度 //3.遍历所有导弹 int flag; //用flag表示导弹i有没有被当前导弹系统拦截 for(int i=2; i<=n; i++) { //依次考察敌方导弹daodan[2...n]的高度。 flag=0; // 每次重置为0，表示还没有被拦截 for(int j=1; j<=k; j++) { //遍历所有当前的系统，寻找能拦截该导弹的系统，K是当前导弹的数量 if(lanjie[j]>=daodan[i]) { //找到了，如果当前拦截系统j的最低高度lanjie[j]比daodan[i]要高 //说明了可用，但是没有比较完剩余的拦截系统就不能说最优 //说明当前J这套系统可以拦截，不一定是最优 if(flag==0) { //判断有没有被拦截过 zuobiao=j; //记录当前这一个，为了下面跟剩余的做比较 flag=1; //表示用过 } else if(lanjie[zuobiao] > lanjie[j]) { //用当前的跟剩余的所有系统做比较，找到最低的 zuobiao=j; flag=1; } } } if(flag==0) { //说明没有任何一个导弹拦截系统可以拦截当前导弹i k++; //增加一套，k是拦截lanjie[]的下标，k++表示下一套系统 lanjie[k]=daodan[i]; //把当前没有任何系统能拦截的导弹高度给这个新系统 } else { //表示找到过一套系统 } } 【步骤5】补全else
int daodan[100]; //导弹 int lanjie[100]; // 拦截系统 int zuobiao; //2.将第一枚导弹的高度先给第一套拦截系统 int k=1; //拦截系统的数量或拦截系统的编号，初始化为1 lanjie[k]=daodan[1]; // 第一个导弹的高度给第一个系统最低拦截高度 //3.遍历所有导弹 int flag; //用flag表示导弹i有没有被当前导弹系统拦截 for(int i=2; i<=n; i++) { //依次考察敌方导弹daodan[2...n]的高度。 flag=0; // 每次重置为0，表示还没有被拦截 for(int j=1; j<=k; j++) { //遍历所有当前的系统，寻找能拦截该导弹的系统，K是当前导弹的数量 if(lanjie[j]>=daodan[i]) { //找到了，如果当前拦截系统j的最低高度lanjie[j]比daodan[i]要高 //说明了可用，但是没有比较完剩余的拦截系统就不能说最优 //说明当前J这套系统可以拦截，不一定是最优 if(flag==0) { //判断有没有被拦截过 zuobiao=j; //记录当前这一个，为了下面跟剩余的做比较 flag=1; //表示用过 } else if(lanjie[zuobiao] > lanjie[j]) { //用当前的跟剩余的所有系统做比较，找到最低的 zuobiao=j; flag=1; } } } if(flag==0) { //说明没有任何一个导弹拦截系统可以拦截当前导弹i k++; //增加一套，k是拦截lanjie[]的下标，k++表示下一套系统 lanjie[k]=daodan[i]; //把当前没有任何系统能拦截的导弹高度给这个新系统 } else { //在找到的基础上更新那个系统的最低高度 lanjie[zuobiao]=daodan[i]; } } 【步骤6】
输出k
(adsbygoogle = window.adsbygoogle || []).push({});