CodeForces 23B （图论 思维）

n people came to a party. Then those, who had no friends among people at the party, left. Then those, who had exactly 1 friend among those who stayed, left as well. Then those, who had exactly 2,3,...,n-12,3,...,n−1 friends among those who stayed by the moment of their leaving, did the same.

What is the maximum amount of people that could stay at the party in the end?

输入格式

The first input line contains one number tt — amount of tests ( 1<=t<=10^{5}1<=t<=105 ). Each of the following tt lines contains one integer number nn ( 1<=n<=10^{5}1<=n<=105 ).

输出格式

For each test output in a separate line one number — the maximum amount of people that could stay in the end.

题意翻译

现在聚会上有n个人参加，然后依次按照规律离开，第一次是有0个朋友的人离开，第二次是有1个朋友的人离开，第三次是有2个朋友的人离开，之后依次是有3,4,5,6。。n-1个朋友的一次离开，求最后聚会会剩下多少人 输入:第一行一个整数t，表示数据组数，之后t行每行一个整数n 输出:对于每组数据，输出一个答案 1<=t<=100000 1<=n<=100000

Translated by 稀神探女

输入输出样例

输入 #1复制

1
3

输出 #1复制

1

思路：唉， people came to a party. Then those, who had no friends among people at the party, left. Then those, who had exactly 1 friend among those who stayed, left as well. Then those, who had exactly 2,3,...,n-12,3,...,n−1 friends among those who stayed by the moment of their leaving, did the same.

What is the maximum amount of people that could stay at the party in the end?

输入格式

The first input line contains one number tt — amount of tests ( 1<=t<=10^{5}1<=t<=105 ). Each of the following tt lines contains one integer number nn ( 1<=n<=10^{5}1<=n<=105 ).

输出格式

For each test output in a separate line one number — the maximum amount of people that could stay in the end.

题意翻译

现在聚会上有n个人参加，然后依次按照规律离开，第一次是有0个朋友的人离开，第二次是有1个朋友的人离开，第三次是有2个朋友的人离开，之后依次是有3,4,5,6。。n-1个朋友的一次离开，求最后聚会会剩下多少人 输入:第一行一个整数t，表示数据组数，之后t行每行一个整数n 输出:对于每组数据，输出一个答案 1<=t<=100000 1<=n<=100000

Translated by 稀神探女

输入输出样例

输入 #1复制

1

3

输出 #1复制

1

思路：唉，真的要多练练思维，题意是一开始没有朋友的人走，然后有一个的走，有两个的走......直到有n-1个朋友的走，

那么我们如果能想清楚一点的话这道题其实就不难了，我们要使最后剩下来的人最多，那么必须要使先走的人造成让剩下来的人的朋友数-1，这样就可以跳过踢出剩下这些人的环节了，最好的情况是两个人只有n-2个朋友，然后他们先在其他n-2个人前面被踢出，然后其他n-2个人原来是有n-1个朋友，现在只有n-2个朋友但是现在是踢出n-1个朋友的环节了，所以这n-2个人还保留着，可以去证明，n-2是可以保留最多的人数

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
template <typename T> inline void read(T& x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
int main()
{
	ll t;
	cin>>t;
	for(rg i=1;i<=t;i++)
	{
		ll n;
		cin>>n;
		cout<<max(0ll,n-2)<<endl;
	}
    return 0;
    
}