电子科技大学链时代工作室招新题C语言部分---题号E

1. 题目

  这道题大概的意思是说，一座城市中被埋了许多雷（用一个只含0和1的字符串表示城市，1代表有雷，0代表无雷）。

你作为一个排雷兵，需要花最少的钱引爆所有的雷来使城市中不再有雷（太逆天了，不知道是不是我理解错了，但总之就是要少花钱，还要引爆所有雷）。

当一个雷被引爆时，相邻的雷都会爆炸，所以你可以选择在没有雷的地方埋雷，使得两片雷区连起来，这样你就可以只花一次引爆需要的钱来引爆两片雷区。当然，埋雷也要花钱，不过在大多数案例中，埋雷的花费会较少。

输入

第一行输入一个整形t(1<=t<=100000)，表示接下来需要进行几轮排雷。

对于每一次排雷，第一行分别输入引爆雷和埋雷的花费(a和b, 且1<=a,b<=1000)，第二行输入一个只含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.h>int 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] == '1'&&arr[i-1] == '0')//a数量加一，结算前方0{if(a <= b * count)a_num++;elseb_num = count;count = 0;}else if(arr[i] == '1'&&arr[i-1] == '1')//连续一无意义{;}else if(arr[i] == '0'&&arr[i-1] == '1')//开始统计零{count++;flag2 = 1;}else if(arr[i] == '0'&&arr[i-1] == '0'&&flag2)//连续零统计{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.h>int 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 == '0'&&e <= f){e++;};while(*f == '0'&&e <= 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 += (kong+1) * a;num[i] = coin;}for(int i = 0; i < n; i++){printf("%d\n", num[i]);}free(num);return 0;
}

3.3 总结

能用通用算法的，绝不用if语句来处理特使情况。

所以千万不要放弃一个较好的算法而去尝试暴力解法。