CodeForces 1249A --- Yet Another Dividing into Teams
【CodeForces 1249A --- Yet Another Dividing into Teams】
Description
You are a coach of a group consisting of n students. The i-th student has programming skill ai. All students have distinct programming skills. You want to divide them into teams in such a way that:
No two students i and j such that |ai−aj|=1 belong to the same team (i.e. skills of each pair of students in the same team have the difference strictly greater than 1);
the number of teams is the minimum possible.
You have to answer q independent queries.
Input
The first line of the input contains one integer q (1≤q≤100) — the number of queries. Then q queries follow.
The first line of the query contains one integer n (1≤n≤100) — the number of students in the query. The second line of the query contains n integers a1,a2,…,an (1≤ai≤100, all ai are distinct), where ai is the programming skill of the i-th student.
Output
For each query, print the answer on it — the minimum number of teams you can form if no two students i and j such that |ai−aj|=1 may belong to the same team (i.e. skills of each pair of students in the same team has the difference strictly greater than 1)
Sample Input
4
4
2 10 1 20
2
3 6
5
2 3 4 99 100
1
42
Sample Output
2
1
2
1
解题思路:题目要求同一分组内任意两个数的差值不等于1,仔细相一下,那么只要相邻的数不在同一个的分组内,这样一想,只要存在一对相邻的数那么就有两个分组,那么其实也就需要两个分组就足够了,其他数字分别进入这两个分组就好。为了减小时间复杂度,先将所有数字快排一遍,在遇到第一对相邻的数差值=1时,跳出循环。
AC代码:
#include <iostream>
#include <algorithm>
using namespace std;
int a[];
int main()
{
int q,n;
int flag=;
while(cin>>q)
{
for(int i=;i<q;i++)
{
cin>>n;
flag=;
for(int j=;j<n;j++)
cin>>a[j];
sort(a,a+n);
for(int k=;k<n-;k++)
{
if(a[k+]-a[k]==)
{
flag=;
break;
}
}
if(flag==)
cout<<<<endl;
else
cout<<<<endl;
} }
return ;
}
最新文章
- Entity Framework Code First实体对象变动跟踪
- EF6 的性能优化
- 在android 中开发java.net.SocketException: socket failed: EACCES (Permission denied) 报错
- java获取classpath
- 使用BeanNameAutoProxyCreator实现spring的自动代理
- python的中文编码问题
- MS对WCF配置中security节点的解释
- HDU2896+AC自动机
- poj3167
- Android驱动之 Linux Input子系统之TP——A/B(Slot)协议
- 求n!末尾0的个数
- CountDownLatch 源码解析—— countDown()
- MongoDB 连接
- string_array.go
- 蓝桥杯 穿越雷区(bfs)
- 【LeetCode每天一题】Plus One(加一)
- 修改minifest使桌面软件支持高dpi
- POJ 3352 Road Construction ; POJ 3177 Redundant Paths (双联通)
- Tomcat 配置详解/优化方案(转)
- Linux 应用——常用函数(usual function)