Codeforces Global Round 16 - A

题目翻译

给你两个正整数 n 和 s。找到含 n 个非负整数的数组最大的可能的中值（不一定不同），使其元素之和为 s。

长度为 m 的整数数组中值是基于在非递减元素序列的第 [m/2]（取整）位置。位置从 1 开始编号。举个栗子，数组[20,40,20,50,50,30]的中值是数组中第 [m/2]（取整）位置，也就是 30。中值还有其他的定义，但是这个问题我们用描述的定义。

输入

输入由多个测试样例组成，第一行包含单个数字 t （1≤t≤1e4）- 测试样例的个数。测试样例的描述如下。

每个样例包含单独一行有两个数字 n 和 s（1≤n，s≤1e9）- 数组的长度和所需的元素和。

输出

对于每个测试用例，打印一个整数 - 最大可能中值数

样例

输入

8
1 5
2 5
3 5
2 1
7 17
4 14
1 1000000000
1000000000 1
 

输出

5
2
2
0
4
4
1000000000
0
 

注释

前三个测试用例的可能数组（在每个数组中，中值加下划线）：

• 在第一个样例中 [5]
• 在第二个样例中 [2,3]
• 在第三个样例中[1,2,2]

解题思路

题目说了数组中的值可以相同，还要求中值最大，那我们就分开奇数和偶数，按照题目要求取得中值，为了使中值最大，我们可以将 s/(n-cnt+1) 作为最大中值。

代码示例

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
int t;
int n,s;
int cnt;
 
int main(){
	cin>>t;
	while(t--){
		cin>>n>>s;
		if(n%2==0) cnt=n/2;
		else cnt=n/2+1;
		cout<<s/(n-cnt+1)<<endl;
	}
}