洛谷题目:找出次品

T130870 找出次品

题目背景

题目描述

给定一串小球,其中有一个是次品(次品会轻一些)。正常小球用1表示,次品小球用0表示,要求将次品小球的编号找出(编号从11开始) 要求:

  1. 需定义一个天平函数int balance(bool *a, int a_count, bool *b, int b_count),a和b均为小球数组,a_count、b_count为两数组所含小球的数量。若a重,则返回1;b重,则返回-1;a,b等重,返回0。
  2. 利用天平函数,设计递归算法来进行题目给出的小球次品的寻找。

输入格式

第一行一个整数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;
}

人已赞赏
经验教程

SpringMVC-01 什么是SpringMVC

2021-3-4 22:29:00

经验教程

Java跨平台原理与Java虚拟机(JVM)

2021-3-4 22:34:00

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索