怎么查找一个网站开发时间,福田网站建设团队,德清县建设银行官方网站,建设网站公司推荐1. 题目 问题的第一段也是非常逆天#xff0c;说实话#xff0c;你编不出问题背景可以不编。
这道题的大概意思就是#xff0c; Pia要去坐飞机#xff0c;那么行李就有限重。这时Pia想到自己带了个硬盘#xff0c;众所周知#xff0c;硬盘上存储的数据就是0和1的二进制序…1. 题目 问题的第一段也是非常逆天说实话你编不出问题背景可以不编。
这道题的大概意思就是 Pia要去坐飞机那么行李就有限重。这时Pia想到自己带了个硬盘众所周知硬盘上存储的数据就是0和1的二进制序列。
对于一段二进制序列每有一个从0到1的过渡或是从1到0的过渡也就是每有一个0和1的分界就会导致硬盘的重量轻微增加一点为了不超重Pia就需要修改一下硬盘上存储的数据。
然而硬盘上的某些位置是坏掉的坏掉的位置只能存入0其中第一个位置永远是好的最后一个位置永远是坏的。
输入
第一行分别输入三个数ncb2n5.1c,bn-1。
n表示二进制序列的长度c表示所需分界位置的数量b表示损坏位置的个数。
第二行输入损坏位置的位置信息。
输出
输出符合条件的二进制序列。 2. 第一版解法
2.1 思路
1. 首先我们肯定需要依据n开辟一个数组但接下来我们就有两种选择将数组元素全部初始化为0或全部初始化为1。
2. 如果我们将数组全部初始化为0那么我们在将某个元素改为1时需要先检查其是否为损坏的位置每次都需要遍历储存位置信息的数组。
3. 如果我们将数组初全部始化为1那么我们只需要在初始化结束之后把损坏的位置改为0即可并在之后的过程中确保只将1改为0而不将0改为1。
4. 第一个位置始终是好的最后一个位置始终是坏的。这个条件对边界上的位置进行了限制边界上的位置有什么特殊的吗
我们发现边界上出现1最多只会导致1次变化而中间位置上出现1不与边界1相连一定会导致2次变化。
所以如果题上要求的变化次数为奇数那么一号位一定是1如果题上要求的变化次数为偶数则一号位上一定不是1。
add原本指向数组开头这里将与一号位相连的1都抛开不看了(有问题下一版会该)
if(c%2 0)
{bit[0] 0;
}
else
{bit[0] 1;c--;//所需减一while(*(add) 1);
}
5. 在将一号位调整好之后就可以先将其抛开不看了将add当作数组开头进行进一步调整。
6. 接下来我们的做法是记录每一段1的起始与结束位置如果当前发生字节改变的位置比要求的少那么就将某一段1分割为两段中间用0隔开如果当前发生字节改变的位置比要求的多那么就将某一段1全部置为0。
2.2 代码
#include stdio.h
#include stdlib.h
#include string.htypedef struct posi
{char* start;char* end;
}posi;int main()
{int n 0, c 0, b 0, count 0;//硬盘大小所需字节改变处数量受损坏字节数量1的段数char sep[] {0};scanf(%d %d %d, n, c, b);char* bit (char*)malloc(sizeof(char) * (n 1));//存结果bit[n] \0;bit[n-1] 0;char* add bit;for(int i 0; i n - 1; i){bit[i] 1;}int* Bre (int*)malloc(sizeof(int) * b);//损坏字节的位置for(int i 0; i b; i){scanf(%d, Bre[i]);bit[Bre[i]-1] 0;}if(c%2 0){bit[0] 0;}else{bit[0] 1;c--;//所需减一while(*(add) 1);}posi* ret (posi*)malloc(sizeof(posi) * n / 2);for(ret[count].start strtok(add, sep); ret[count].start ! NULL; ret[count].start strtok(NULL, sep))//记录每段1的起始和结束位置{char* tmp ret[count].start;while(*tmp ! \0){tmp;}ret[count].end tmp - 1;}int i 0;if(count 0){if(add bite 32 * count ! c)//1111110{bit[1] 0;ret[count].start bite 2;ret[count].end add - 1;count;}else//10000000{printf(%s\n, bit);free(bit);free(Bre);free(ret);return 0;}}while(2 * count ci n / 2)//改变的少了{if(ret[i].end - ret[i].start 2){*(ret[i].start 1) 0;ret[count].start ret[i].start 2;ret[count].end ret[i].end;count;ret[i].end ret[i].start 1;}else{i;}}while(2 * count ci n / 2)//改变的多了{while(ret[i].start ret[i].end){*(ret[i].start) 0;*(ret[i].end--) 0;}i;count--;}for(int j 0; j n; j){if(bit[j] \0)bit[j] 0;}printf(%s\n, bite);free(bit);free(Bre);free(ret);return 0;
}
2.3 总结
这一段代码的问题就在于add那里将开头连续的1一并忽视掉。
这就会导致需要单独处理一开始就只有开头连续1的情况我们已经说过当你开始考虑特殊情况时你就已经输了一半。
不止如此这还会导致我们能产生的最多字节变化的数量减少因为开头的连续1也可以断开产生更多变化字节。 3. 最终版解法
3.1 思路
这一版就将add给删除了当b为奇数时将一号位置为1然后直接将二号位置为0。
这样做就可以达到目的了而且无需考虑特殊情况可以说add这个变量简直是画蛇添足。
3.2 代码
#include stdio.h
#include stdlib.h
#include string.htypedef struct posi
{char* start;char* end;
}posi;int main()
{int n 0, c 0, b 0, count 0;//硬盘大小所需字节改变处数量受损坏字节数量1的段数char sep[] {0};scanf(%d %d %d, n, c, b);char* bit (char*)malloc(sizeof(char) * (n 1));//存结果bit[n] \0;bit[n-1] 0;for(int i 0; i n - 1; i){bit[i] 1;}int* Bre (int*)malloc(sizeof(int) * b);//损坏字节的位置for(int i 0; i b; i){scanf(%d, Bre[i]);bit[Bre[i]-1] 0;}if(c%2 0){bit[0] 0;}else{bit[0] 1;bit[1] 0;c--;//所需减一}posi* ret (posi*)malloc(sizeof(posi) * n / 2);for(ret[count].start strtok(bite 1, sep); ret[count].start ! NULL; ret[count].start strtok(NULL, sep))//记录每段1的起始和结束位置{char* tmp ret[count].start;while(*tmp ! \0){tmp;}ret[count].end tmp - 1;}int i 0;while(2 * count ci n / 2)//改变的少了{if(ret[i].end - ret[i].start 2){*(ret[i].start 1) 0;ret[count].start ret[i].start 2;ret[count].end ret[i].end;count;ret[i].end ret[i].start 1;}else{i;}}while(2 * count ci n / 2)//改变的多了{while(ret[i].start ret[i].end){*(ret[i].start) 0;*(ret[i].end--) 0;}i;count--;}for(int j 0; j n; j){if(bit[j] \0)bit[j] 0;}printf(%s\n, bit);free(bit);free(Bre);free(ret);return 0;
}
3.3 总结
还是那句话当你的代码需要考虑特殊输入情况时你就要想办法改改它了尽管它看起来万无一失。
