Duizi and Shunzi HDU
2024-09-26 17:26:54
Duizi and Shunzi
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2883 Accepted Submission(s): 1110
Problem Description
Nike likes playing cards and makes a problem of it.
Now give you n integers, ai(1≤i≤n)
We define two identical numbers (eg: 2,2) a Duizi,
and three consecutive positive integers (eg: 2,3,4) a Shunzi.
Now you want to use these integers to form Shunzi and Duizi as many as possible.
Let s be the total number of the Shunzi and the Duizi you formed.
Try to calculate max(s).
Each number can be used only once.
Input
The input contains several test cases.
For each test case, the first line contains one integer n(1≤n≤106).
Then the next line contains n space-separated integers ai (1≤ai≤n)
Output
For each test case, output the answer in a line.
Sample Input
7
1 2 3 4 5 6 7
9
1 1 1 2 2 2 3 3 3
6
2 2 3 3 3 3
6
1 2 3 3 4 5
Sample Output
2
4
3
2
Hint
Case 1(1,2,3)(4,5,6)
Case 2(1,2,3)(1,1)(2,2)(3,3)
Case 3(2,2)(3,3)(3,3)
Case 4(1,2,3)(3,4,5)
Source
题意:输入一个n,然后输入n张牌,每张牌都不大于n,问可以组成最多的对子数和顺子数,对子是两个相同的牌,顺子是连续的三张牌
思路:从1到n遍历, 如果第 i 张牌能打完对子还有多一张,那么看 i+1 张打完对子是不是可以多,如果多的话只要 i+2 有这张牌就可以打出一个顺子,在计算第 i 张牌的时候记得把对子的数量加进去,在可以组成顺子的时候记得把 第 i+1 和 i +2 凑顺子的那一张牌减掉。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
#define PI acos(-1.0)
#define _e exp(1.0)
#define ll long long
const int maxn=1e6+5;
int a[maxn];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(a,0,sizeof(a));
int t;
for(int i=0;i<n;i++)
{
scanf("%d",&t);
a[t]++;
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=a[i]/2;
if(i<=n-2 && a[i]%2 && a[i+1]%2 && a[i+2])
{
ans++;
a[i]--;
a[i+1]--;
a[i+2]--;
}
}
printf("%d\n",ans);
}
}
最新文章
- iOS-多线程基础
- linux中chmod更改文件权限命令
- C#标准响应数据
- C#之你懂得的反射
- Couchbase 找回登录密码
- C语言阶乘和求闰年
- byte[] 清空
- C#网络编程简单实现通信小例子-2
- Ubuntu 14.04为浏览器添加Flash插件
- eclipse 配置android sdk和maven
- java 之 命令模式(大话设计模式)
- 如何导入外部的源码到eclipse中
- 给 Android 开发者的一点福利:免费模拟面试
- sqlserver 删除表 视图 函数 存储过程
- html5 - Storage 本地存储
- FileInputStream与FileOutputStreawm实现文件的加密与解密
- Delphi使用iTools安卓模拟器
- centos 打包报错License for package Android SDK Build-Tools 25.0.3 not accepted
- silverlight 定时器 System.Windows.Threading.DispatcherTimer
- 〖Linux〗Shell十进制数值转换十六进制