钢板填坑问题
路面有n个坑，需要用m个钢板盖住
m个钢板钱不一样，尺寸不一样
固定给出m个钢板，看怎么组合能用总费用最少的钢板盖住所有坑
例
2 3
50 80
50 5 90 3 80 4
结果1 7
给定2个坑，3个钢板
每个坑的直径
每个钢板的直径和费用且成对出现
最后计算是第一个案例，最少使用的费用是7
思路是按费用排序，每次最少费用的钢板该直径最大的坑，保证这一个钢板肯定只能盖住这一个坑。这样后面的钢板
也能对应盖一个坑
3
2 3
50 80
50 5 90 3 80 4
3 5
50 80 40
50 5 79 3 70 4 75 7 40 5
5 10
50 40 50 60 50
50 54 60 11 45 22 49 51 35 16 80 53 70 1 80 99 90 84 55 23
给定框架
package sasst.web;
import java.util.Scanner;
public class Solution {
static int N,M;
static int Hi[] = new int[1000];
static int Si[] = new int[10000];
static int Pi[] = new int[10000];
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int T = sc.nextInt();
for(int test_case =1;test_case<=T;++test_case){
N=sc.nextInt();
M=sc.nextInt();
for(int i = 0;i Hi[i]=sc.nextInt();
}
for(int i =0; i Si[i]=sc.nextInt();
Pi[i]=sc.nextInt();
}
System.out.println();
System.out.println("keng size ");
for(int i = 0;i System.out.print(Hi[i]+" ");
}
System.out.println();
System.out.println("gangban ");
for(int i =0; i System.out.print(Si[i]+" "+Pi[i]+" ");
}
System.out.println();
}
}
}
具体实现
注意
前面数组构造时的长度，改成N,M，而不是1000具体值，以防后面比较时数组中出现大量0影响排序结果
new时候的语句要在输入以后，而不是最上面声明
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Solut {
static int N,M;
static int Hi[];
static int Si[];
static int Pi[];
static MtDate[] mtDate;
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int T = sc.nextInt();
for(int test_case =1;test_case<=T;++test_case){
N=sc.nextInt();
M=sc.nextInt();
Hi = new int[N];
for(int i = 0;i Hi[i]=sc.nextInt();
}
Si=new int[M];
Pi=new int[M];
mtDate = new MtDate[M];
for(int i =0; i Si[i]=sc.nextInt();
Pi[i]=sc.nextInt();
mtDate[i]=new MtDate();
mtDate[i].Si = Si[i];
mtDate[i].Pi = Pi[i];
}
Comparator mt = new MyT();
Arrays.sort(mtDate,mt);
Arrays.sort(Hi);
int price = 0;
for(int i=N-1;i>=0;i--){
int t = getPrice(Hi[i]);
if(t>0)price=price+t;
else {price=-1; break;}
}
System.out.println();
System.out.print(test_case+","+price);
}
}
static int getPrice(int hhi)
{
for(int i=0;i if(mtDate[i].Si>=hhi&&!mtDate[i].used){
mtDate[i].used=true;
return mtDate[i].Pi;
}
}
return -1;
}
}
class MtDate{
public int Si,Pi;
public boolean used= false;
}
class MyT implements Comparator{
public int compare(MtDate o1,MtDate o2){
if(o1.Pi return -1;
}else if(o1.Pi>o2.Pi){
return 1;
}else{
return 0;
}
}
}
20170713 真算法
查找避难所个数
1 2 3 7 8 9
2 9 8 6 5 2
2 3 2 5 6 7
1 2 3 2 6 8
2 3 1 5 7 9
如上面数组，每行值表示海拔高度，发大水时寻找紧急避难所，需要根据海拔高度判断
避难所的最大个数。
给定测试用例
5 5 7 数组的长和宽 7是洪水高度
然后找避难所时，避难所得海拔高度要高于即>洪水高度。符合要求的避难所必须是在其
上下左右至少一个方向里也有一个符合要求的避难所。同时重要的是还要找到避难所的最大
个数。比如这里洪水高度是7，那么8和9符合要求，但矩阵中有多个8和9，这是相当于有
三处避难所，而每个避难所的个数都是2，因此找出的避难所个数最大是2.可想如果矩阵
中有一处是8和9,10，另一处是8和9，那么最大避难所的个数是3而不是2.
自己的实现思路是双循环，每一个元素查找时判断前后左右四个方向是不是有挨着的。
如果判断这个值符合条件，就继续判断这个值得坐标和迁移符合要求的元素的值坐标
是不是挨着如果挨着计数器继续增加，不挨着计数器将为0，这样找出最大的count。
注意 寻找前一个坐标是要初始化prei=-1，prej=-1 因此第一个符合条件的值的坐标count++,prei=i,prej=j
以后符合条件值的坐标要判断该点坐标和前一个点坐标是否挨着再count++,且prei=i,prej=j
20170727
32位字符数，如10000000000000000000000000000000 和 00000000000000000000000000000001
左边的数中1可以向左或向右移动，问向哪边移动次数最少可以移动成为右边的数字
移动结果L 1 向左移动一次是右面数字
0000000000000000000000000010101 0000000000000000000000000000001
左面没法移动成右面所以结果是 -1
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
软考中级精品资料免费领
历年真题答案解析
备考技巧名师总结
高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1148
183.71 KB下载数642
644.84 KB下载数2756
相关文章
发现更多好内容猜你喜欢
AI推送时光机计算机软考高级论文历年真题
Java算法真题详解运用单调栈
H3C HSE 考试真题
PHP浮点数运算精度失真问题的深入分析
软件设计师算法基础及常见算法考点
Java算法练习题,每天进步一点点(1)
Java算法练习题,每天进步一点点(2)
软考「网工」备考资料看这里！历年真题、易混淆知识点……
2018软考初级真题汇总
考后发布2019年9月计算机一级考试真题及答案通知
考后发布2019年9月全国计算机等考真题及答案通知
软件设计师中级考试真题，软考中级软件设计师历年真题
如何从历年真题中掌握网络管理员重要考点？
2021年软件设计师考点：算法基础及常见算法
LeetCode 算法题真的能帮助你提升编程能力吗？
2010年9月全国计算机二级Access考试真题及答案
2017软考程序员真题汇总
计算机软考考点在哪？
