大佬教程收集整理的这篇文章主要介绍了洛谷题目:找出次品,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
给定一串小球,其中有一个是次品(次品会轻一些)。正常小球用1表示,次品小球用0表示,要求将次品小球的编号找出(编号从11开始) 要求:
第一行一个整数n,表示小球的数量。
第二行n个整数,其中1个为0,其余n-1个为1,请找出次品的编号。
一个整数(1…n),表示次品的位置。
输入 #1
5
1 1 1 0 1
输出 #1
4
1≤n≤1,000
#include<iostream>
using namespace std;
int find(int* weight, int left, int right) {//首次传入的left为数组最左边的一个下标,首次传入的right为数组最右边的一个下标,返回值为次品所对应的数组下标
if (left + 1 == right) {//如果仅有两个球 或 递归算法进行到仅剩两个球的时候
return weight[left] < weight[right] ? left : right;
}
int mid = left + (right - left) / 2;//中间位置的小球
int Lsum = 0, Rsum = 0;//Lsum表示左侧天平所有小球的质量,Rsum表示右侧天平所有小球的质量
if ((right - left + 1) % 2 == 0) {//如果有(大于2的)偶数个球
for (int i = left; i <= mid; ++i) {
Lsum += weight[i];
}
for (int i = mid + 1; i <= right; ++i) {
Rsum += weight[i];
}
return Lsum < Rsum ? find(weight, left, mid) : find(weight, mid + 1, right);//返回质量较轻的一组进行递归
}
else {//如果有(大于1的)奇数个球
for (int i = left; i <= mid-1; ++i) {
Lsum += weight[i];
}
for (int i = mid + 1; i <= right; ++i) {
Rsum += weight[i];
}
//此时表示将中间小球拿出,剩下偶数个小球,Lsum为mid左侧所有小球的质量,Rsum为mid右侧所有小球的质量
if (Lsum == Rsum)return mid;//如果左右两侧小球的质量相同,返回中间位置小球的下标
else return Lsum < Rsum ? find(weight, left, mid-1) : find(weight, mid + 1, right);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int* weight = new int[n];
for (int i = 0; i < n; ++i) {
cin >> weight[i];
}
if (n == 1) {
cout << 1;//如果仅有一个球,默认此球即为次品
}
else cout << find(weight, 0, n - 1) + 1 << endl;
delete[]weight;
return 0;
}
以上是大佬教程为你收集整理的洛谷题目:找出次品全部内容,希望文章能够帮你解决洛谷题目:找出次品所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。