微信订阅号不认证可以做网站吗,最便宜建站,建设简单网站,麻城网站制作公司题目#xff1a; 思路#xff1a;
先在所有树中找到最长的树#xff0c;从 1 到 这个最长的树的长度 的所有数作为二分查找的值#xff0c;让每棵树除这个值#xff0c;表示可以切出几段出来#xff0c;累加在一起得到s#xff0c;s表示一共有几段。s与k比较#xf…题目 思路
先在所有树中找到最长的树从 1 到 这个最长的树的长度 的所有数作为二分查找的值让每棵树除这个值表示可以切出几段出来累加在一起得到ss表示一共有几段。s与k比较如果sk表示找到了切出每段的长度但此时并不能就结束了也有可能这个长度再长一点也可以切出我们要的k段。
一开始写的错误代码
#includestdio.h
int cmp(const void *a,const void *b){return *(int *)a-*(int *)b;
}
int main(){long long n,k;//n是指有n根原木k是指切出k段 scanf(%lld %lld,n,k);int i;long long tree[1000005];for(i0;in;i){scanf(%lld,tree[i]);}long long sum0;for(i0;in;i){sumtree[i];} if(sum/k0){printf(0);return 0;} qsort(tree,n,sizeof(tree[0]),cmp);long long left1;long long righttree[n-1];long long s0;while(leftright){s0;long int mid(leftright)/2;for(i0;in;i){stree[i]/mid;}if(sk){leftmid1;}else if(sk){rightmid-1;}else{printf(%lld,mid);break;}}return 0;
}
错就错在了我把sk的情况单独分出来然后就break了。
正确的代码
#includestdio.h
int max(int a,int b){if(ab){return a;}else{return b;}
}
int main(){long long n,k;//n是指有n根原木k是指切出k段 scanf(%lld %lld,n,k);int i;long long tree[1000005];long long max10;for(i0;in;i){scanf(%lld,tree[i]);max1max(tree[i],max1);}long long sum0;for(i0;in;i){sumtree[i];} if(sum/k0){printf(0);return 0;} long long left1;long long rightmax1;long long s0;long long ans;while(leftright){s0;long long mid(leftright)/2;for(i0;in;i){stree[i]/mid;}if(sk){leftmid1;}else{rightmid-1;}}printf(%lld,left-1);return 0;
} 我们来重点分析这一段 if(sk){leftmid1;}else{rightmid-1;}
printf(%lld,left-1);
其实这种只写两种情况很好理解当找到sk时left会继续往右走跨过当前我们找到的这个mid的值 如果右边还存在可以满足我们要的sk的情况就会继续进入sk的条件下然后left又会跨过我们要的mid的值而如果右边范围不存在sk或者sk也不成立那么就只会一直进入rightmid-1此时left一直没动right一直在往左移直到right移到了left左边循环结束输出left-1就是我们当时要的mid值。
有个问题需要注意的是为什么这个sk的情况要连在sk一起写而不是和sk因为当找到sk的情况时我们还要再找有没有就是可以切出更长段的k段所以肯定是要往数值大的方向去找所以执行的语句是leftmid1而不是rightmid-1
其实也可以拆开写 if(sk){leftmid1;}else if(sk){rightmid-1;}else{leftmid1;} printf(%lld,left-1);
