Problem Statement
|
|
Dmitry likes TopCoder Single Round Matches. Once, he registered for an SRM and was waiting for the coding phase to begin. To entertain himself while waiting, he decided to play the following game.
He makes a pile of cards, and on each card, he writes the number of an SRM in which he has competed. No two cards contain the same number. He then takes turns until the pile is empty. Each turn consists of the following sequence of actions:
- Dmitry chooses an arbitrary card from the pile. Let A be the number written on this card.
- The card with number A is removed from the pile.
- If the pile contains a card with number A-1, that card is removed from the pile.
- If the pile contains a card with number A+1, that card is removed from the pile.
The game is finished when the pile becomes empty. It's fun to play the game, so Dmitry wants to spend as much time as possible playing it.
You are given a vector <int> cards containing the numbers written on the cards in the pile before the start of the game. Return the largest possible number of turns in which Dmitry can finish the game. |
Definition
|
|
Class: |
SRMCards |
Method: |
maxTurns |
Parameters: |
vector <int> |
Returns: |
int |
Method signature: |
int maxTurns(vector <int> cards) |
(be sure your method is public) |
|
|
|
Constraints
|
- |
cards will contain between 1 and 50 elements, inclusive. |
- |
Each element of cards will be between 1 and 499, inclusive. |
- |
All elements of cards will be distinct. |
Examples
|
0) |
|
|
|
Returns: 1
|
In the first turn, Dmitry can choose A = 498 or A = 499. In any of these cases both cards will be removed from the pile and the game will be finished. |
|
|
1) |
|
|
{491, 492, 495, 497, 498, 499}
|
|
Returns: 4
|
One out of many possible ways to spend 4 turns playing this game is to choose the following numbers in each turn: 497, 499, 495, 492. |
|
|
2) |
|
|
|
3) |
|
|
{11, 12, 102, 13, 100, 101, 99, 9, 8, 1}
|
|
Returns: 6
|
Note that the elements of cards are not necessarily sorted in ascending order. |
|
|
4) |
|
|
{118, 321, 322, 119, 120, 320}
|
|
Returns: 4
|
|
|
5) |
|
|
{10, 11, 12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9}
|
|
Returns: 7
|
|
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
【题解】
贪心即可。
【代码】
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class SRMCards {
public:
int maxTurns(vector <int>);
};
int SRMCards::maxTurns(vector <int> cards)
{
sort(cards.begin(),cards.end());
int ans=0,i;
for (i=0;i<cards.size();i++)
{
if (i<cards.size()-1 && cards[i+1]==cards[i]+1)
{
ans++;i++;
}
else ans++;
}
return ans;
}
//Powered by [KawigiEdit] 2.0!
分享到:
相关推荐
topcoder-srm Topcoder SRM竞赛解决方案 测试是使用kawigi edit构建的。
你可以通过这道题去了解Topcoder的题目以及比赛形式
关于TopCoder的竞赛指导,不仅仅是SRM,还有Bug Race、软件比赛的资料,是我从网上收集的,大部分是中文的
TopCoder SRM程序 我尝试过的TopCoder SRM程序列表。 在大多数时候,比赛时间与我的工作/其他活动冲突,因此我对TopCoder不太活跃。 但是我尽力去参加比赛,因为这很有趣。 就像在任何在线比赛中所期望的那样,代码...
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
topcoder-srm 顶级编码器srm问题集锦
topcoder竞赛的算法讲座ppt
topcoder算法讲座ppt
Topcoder软件比赛注册方法和平台使用 Topcoder算法大赛客户端安装流程 Topcoder算法大赛客户端登陆及使用 Topcoder算法大赛注册流程 Topcoder图形比赛注册方法和平台使用
适合topcoder新手
TopCoder比赛登录使用的客户端,需要配置Java环境
TopCoder新手入门指南,一步步操作既可以了,然后开启您的Topcoder编程之旅吧。
Topcoder的Java客户端,安装前确定已经安装了JRE
topcoder arena,包含ContestAppletProd.jnlp,CodeProcessor.jar,FileEdit.jar,TZTester,运行需要jre环境
用于topcoder的第3方编辑器插件。
TopCoper SmartWordToy problem 解决方法,C++源码。 Problem Statement The toy company "I Can't Believe It Works!...Form: http://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532
topcoder的比赛作品,编译通过的。可以放心使用。
topcoder入门,对想做tc,但又不知道怎么搞的很有帮助,我首先也不知道搞。
给新手提供的TopCoder注册方法和平台使用 十分详细
这是一类关于acm学习的资料,它详细的说明了Acm学习的内容,如何提高编写软件的能力