非减序列是：1, 2, 2, 3, 3, 4。第4个数字是3，所以 输出3。
一开始我想到的是搜索，从n*m开始搜索，后来发现状态实在太多而且即便是搜索，时间复杂度是O(N * M)。
正确的解法是二分。二分答案（边界是[1, n * m]），然后在乘法表中去找比他小的数。因为乘法表是一个有规律的数表，所以针对每一列直接O(1)计算即可，总共计算N次。
总的时间复杂度是O(N * 2 * log(N))。
代码示例
/*****************************************************************************# COPYRIGHT NOTICE# Copyright (c) 2014 All rights reserved# ----Stay Hungry Stay Foolish----## @author :Shen# @name :D# @file :D.cpp# @date :2014/07/17 22:47# @algorithm :Binary Search******************************************************************************///#pragma GCC optimize ("O2")//#pragma comment(linker, "/STACK:1024000000,1024000000")#include using namespace std;template inline bool updateMin(T& a, T b){ return a > b ? a = b, 1: 0; }template inline bool updateMax(T& a, T b){ return a > n >> m >> k; int64 Right = n * m, Left = 1; int64 ans = BinarySearch(Left, Right); cout
查看更多关于CodeforcesRound#256(Div.2)D二分答案_html/css_WEB-ITnos的详细内容...
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did105316