题目来源:http://community.topcoder.com/stat?c=problem_statement&pm=3457&rd=5869
解答分析:http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm223
这道题目最直接最暴力的算法就是遍历每个位置,然后查看是否满足条件,满足条件的话则立刻停止遍历,
这样算法的时间复杂度为O(N^2)。不过还有一个更高效的方法,其时间复杂度为O(N),只需进行一次遍历
就可以了。该题目的作者给出了最好的解答,如下:
To visualize the O(N) solution, make a graph where the value at positionxis the number of black cards in the firstxcards, minus the number of red cards in the firstxcards.xincreases as each new card is turned over, and the graph goes up one unit
if it is black, and down one unit if it is red.
Here is graph for the "RBBRRRRBBBRBBRRBRBBRRRRBBBBBRRRB":
/\
/\ /\ /\ / \
\/ \ /\/ \/\/ \ / \/
\ / \ /
\/ \/
Notice that this graph ends up at the same level at which it starts, because there are an equal number of red and black cards. If the value ever dips below the starting value (as it does in this graph), that means you lose the game. Cutting the deck is equivalent
to moving the same number of line segments from the front of the graph to the end. So finding the right place to cut the deck is equivalent to finding the right place to cut the graph such that the value never dips below the starting value. This point is,
obviously, at the minimum of the graph. If there are more than one, you select the left-most minimum (corresponding to the cut with the fewest cards.) In this example, that point is seven units from the left, so the answer is 7.
实现该算法的代码如下:
#include <string>
#include <vector>
using namespace std;
class BlackAndRed {
public:
int cut(string deck) {
int res = 0;
int minpoint = 0;
int point = 0;
for (int i = 0; i < deck.size(); i++) {
if ('R' == deck[i]) {
--point;
} else {
++point;
}
if (point < minpoint) {
minpoint = point;
res = i + 1;
}
}
return res;
}
};
分享到:
相关推荐
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 <= N , 1 <= K <= 1000.
SRM WiFi自动登录这是使用Selenium驱动程序进行的SRM wifi连接的自动登录。 在SRM中,只要您想连接到SRM WiFi,就需要连接网络登录页面(即' ')并输入您的登录凭据。 因此,对于我的朋友们,我尝试使用selenium和...
本srm模型为高解析版的Audiojungle声音水印特别处理过的声音模型,理论上支持各种版本的AU去消除Audiojungle的声音水印,操作方式自行查找
SAP SRM 标准教材,官方教程:SRM220 Analytical EBP。
BridgeCrossing.java - SRM 146 DIV 2,1000 点问题,时间复杂度 O(n^(n^3))。 BridgeCrossingOptimized.java - SRM 146 DIV 2,1000 点问题,时间复杂度 O(n^(n^2))。 BridgeCrossingBest.java - SRM 146 DIV 2,...
通过整合供应商关系管理(SRM)和精益范式,本文提出了精益供应商关系管理(LSRM)的概念,并检验了其与企业绩效(FP)的关系。 LSRM实践已确定并映射为:供应灵活性,及时交付,信息集成和供应商合作关系。 使用162...
分块描述SRM系统的作用:寻源、协同和考核 涉及具体的业务用途,供前期规划作参考,可根据实际情况调整,再考虑如何实现
SAP SRM 介绍
srm后端JAVA 供应商平台管理 标准物资开票表 bus_standard_invoice_out增加freeze_quantity(冻结数量这一列)。 标准物资开票表 bus_standard_invoice_out的主键为{行项目、采购订单号、物料凭证}。 标准物资...
Driver HASP SRM emulator (x86)
monofab-SRM-20_Files:安装和使用Roland SRM-20 CNC路由器所需的文件
HASP_SRM_Runtime_setup
多年SRM实施经验总结,对希望从事SRM实施或规划的同学们有帮助
简叙什么是SRM,SRM解决什么问题,SRM有用途,SRM功能等
SRM210 (PA)SAP SRM Server Configuration (Col92) Configuration
SRM空间富模型隐写分析算法,选区高维特征,使用集成分类器进行训练
SRM Overview中文版让你更直观更容易了解SRM是什么,能做什么
SRM影像分割算法的matlab程序,主函数SRM_new
不仅可以阅读srm格式文件,还可以制作文档。完全绿色破解,是一款不错的srm阅读器。
HASP SRM加密狗简介,阿拉丁公司的各种加密够简介