视频网站开发工程师,wordpress导入导出,重庆网络建站,全球搜索1. 题目 这道题大概的意思是说#xff0c;一座城市中被埋了许多雷#xff08;用一个只含0和1的字符串表示城市#xff0c;1代表有雷#xff0c;0代表无雷#xff09;。
你作为一个排雷兵#xff0c;需要花最少的钱引爆所有的雷来使城市中不再有雷#xff08;太逆天了一座城市中被埋了许多雷用一个只含0和1的字符串表示城市1代表有雷0代表无雷。
你作为一个排雷兵需要花最少的钱引爆所有的雷来使城市中不再有雷太逆天了不知道是不是我理解错了但总之就是要少花钱还要引爆所有雷。
当一个雷被引爆时相邻的雷都会爆炸所以你可以选择在没有雷的地方埋雷使得两片雷区连起来这样你就可以只花一次引爆需要的钱来引爆两片雷区。当然埋雷也要花钱不过在大多数案例中埋雷的花费会较少。
输入
第一行输入一个整形t(1t100000)表示接下来需要进行几轮排雷。
对于每一次排雷第一行分别输入引爆雷和埋雷的花费(a和b, 且1a,b1000)第二行输入一个只含0和1的字符串表示城市中埋雷的情况。
对于每次测试各轮排雷输入的字符串的总长度不会超过100000。
输出
依次输出每轮排雷的最低花费。 例如题中所给的例子的第二轮排雷 引爆的花费是5埋雷的花费是1 城市中雷的情况是01101110 于是选择将两片雷区连起来在第四个位置上埋雷再进行引爆总花费是6。 2. 第一版解法 这一版并不完全算作第一版其实是第二版。由于第一版老是通不过于是我气急败坏地写了个暴力解法
2.1 思路
1. 最前端的0不需要考虑因为在这这里埋雷毫无意义于是先将字符串缩短一下使得字符串以1开头。
2. 最后段其实也同样不需要考虑但第一版的解法能够直接无视掉最后一段零如果有的话。
3. 除开这两段无需考虑的零其他每一段零我们都需要考虑是否要埋雷来链接雷区。判断是否要埋雷的逻辑也很简单因为链接一次雷区可以使我少引爆一次所以就判断是埋雷花费高还是多引爆一次花费高。
4. 在不考虑最后一段零的情况下雷区数一定比零的段数多一当每次决定不埋雷时无雷区的数量加加雷区数量就是无雷区数量加一。
5. 遍历字符串用if语句来具体处理每一种情况。
2.2 代码
#include stdio.h
#include stdlib.h
#include string.hint main()
{int n 0;scanf(%d, n);int* num (int*)malloc(sizeof(int) * n);for(int i 0; i n; i){int a 0, b 0, count 0, j 1, a_num 1,b_num 0, flag1 1, flag2 0;char* ret NULL;char arr[100000] {0};scanf(%d%d, a, b);getchar();while((arr[0] getchar()) 0);while((arr[j] getchar()) ! \n){flag1 0;}if(flag1){num[i] 0;continue;}for(int i 1; i j; i){if(arr[i] 1arr[i-1] 0)//a数量加一结算前方0{if(a b * count)a_num;elseb_num count;count 0;}else if(arr[i] 1arr[i-1] 1)//连续一无意义{;}else if(arr[i] 0arr[i-1] 1)//开始统计零{count;flag2 1;}else if(arr[i] 0arr[i-1] 0flag2)//连续零统计{count;}}if(a_num 0){num[i] 0;continue;}num[i] a_num * a b_num * b;}for(int i 0; i n; i){printf(%d\n, num[i]);}free(num);return 0;
}
2.3 总结
前面已经说了这是一气之下写出来的破罐子破摔写法没有什么参考意义。
经过这几天的做题我发现当你开始用if语句来处理各种特殊情况时你就失败一半了。 3. 最终版解法
这一版才是严格意义上的第一版只不过之前由于许多画蛇添足的操作导致程序老是通不过。后来上面那一版也过不了我又回来继续改这一版删掉了几句就过了。
3.1 思路
1. 这一版与上一版的不同在于上一版采用的是依次遍历数组用if语句逐个处理每个元素的方法这一版采用了函数strtok。
2. 我们的目的其实就是找到两端都是1的无雷区那么我们完全可以用strtok函数来将字符串分割出一个个的连续0段然后判断是否要埋雷。
3. 这一次我们需要将尾端的无雷区也消减掉。
3.2 代码
#include stdio.h
#include stdlib.h
#include string.hint main()
{int n 0;scanf(%d, n);int* num (int*)malloc(sizeof(int) * n);for(int i 0; i n; i){int a 0, b 0, count 1, coin 0, kong 0, j 0, flag1 1, flag2 1;char* ret NULL;char arr[100006] {0};char* sep 1;scanf(%d%d, a, b);getchar();while((arr[j] getchar()) ! \n){if(arr[j] 1)flag1 0;if(arr[j] 0)flag2 0;j;}if(flag1){num[i] 0;continue;}if(flag2){num[i] a;continue;}char* e arr;char* f arr j - 1;while(*e 0e f){e;};while(*f 0e f){f--;};*f \0;for(ret strtok(e, sep); ret ! NULL; ret strtok(NULL, sep)){int len strlen(ret);if(len*b a){coin len*b;}else{kong;}}coin (kong1) * a;num[i] coin;}for(int i 0; i n; i){printf(%d\n, num[i]);}free(num);return 0;
}
3.3 总结
能用通用算法的绝不用if语句来处理特使情况。
所以千万不要放弃一个较好的算法而去尝试暴力解法。
