小红的小球染色期望

B-小红的小球染色_牛客周赛 Round 79

题目描述

本题与《F.R小红的小球染色期望》共享题目背景，但是所求内容与范围均不同，我们建议您重新阅读题面。

有 n 个白色小球排成一排。小红每次将随机选择两个相邻的白色小球，将它们染成红色。小红将持续这个操作，请你计算小红操作次数可能的最小值和最大值。

输入描述：

在一行上输入一个正整数 n (1 ≤ n ≤ 10^9) 代表小球数量。

输出描述：

在一行上输出两个正整数，代表小红操作次数可能的最小值和最大值。

输入描述：
在一行上输入一个正整数 n (1 ≤ n ≤ 10^9) 代表小球数量。

输出描述：
在一行上输出两个正整数，代表小红操作次数可能的最小值和最大值。

示例1
------
输入
-----
3

输出
-----
1 1

说明
-----
在这个样例中，第一次选取，一共有两种不同的选取情况：
● 选中第一、二个球；
● 选中第二、三个球。
不管是哪一种选法，染完颜色后均无法继续操作。所以小红能且仅能操作一次，操作次数最小值为 1。

示例2
------
输入
-----
4

输出
-----
1 2

说明
-----
在这个样例中，第一次选取，一共有三种不同的选取情况：
● 选中第一、二个球；
● 选中第二、三个球；
● 选中第三、四个球。
其中，第二种选取方式染色后无法继续操作；而第一、三种选取方式染色后还可以进行一次染色。

思路：

最大值很明显就是n/2，最小值找规律即可如图：

我们可以看见，n/3+（n%3 == 2）就是最小值

代码如下：
 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n;
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	ll maxn,minn;
	maxn = n/2;
	ll t = n % 3;
	if(t == 2)
	minn = n/3+1;
	else
	minn = n/3;
    
	cout << minn << " " << maxn;
	
    return 0;
}