Codeforces 448 D. Multiplication Table
二分法判断答案
Bizon the Champion isn't just charming, he also is very smart.
While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann × m multiplication table, where the element on the intersection of the i-th row and j-th column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th largest number?
Bizon the Champion always answered correctly and immediately. Can you repeat his success?
Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th number you write out is called the k-th largest number.
The single line contains integers n, m and k (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m).
Print the k-th largest number in a n × m multiplication table.
2 2 2
2
2 3 4
3
1 10 5
5
A 2 × 3 multiplication table looks like this:
1 2 3 2 4 6
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; typedef long long int LL; LL n,m,k; bool ck(LL x) { LL nt=0; for(LL i=1;i<=n;i++) { nt+=min(m,x/i); } if(nt>=k) return true; return false; } int main() { scanf("%I64d%I64d%I64d",&n,&m,&k); LL low=1,high=n*m,ans=-1,mid; while(low<=high) { mid=(low+high)/2; if(ck(mid)) { ans=mid; high=mid-1; } else low=mid+1; } printf("%I64d\n",ans); return 0; }
版权声明:来自: 代码代码猿猿AC路 http://blog.csdn.net/ck_boss
相关文章
- 前端Table数据导出Excel使用HSSFWorkbook(Java)
- service mysqld start 报错:service mysqld start 报错 090517 13:34:15 [ERROR] Can't open the mysql.plugin table. Please run mysql_upgrade to create it. 090Can't open the mysql.plugin table. Please run mysql
- ALTER TABLE causes auto_increment resequencing, resulting in duplicate entry ’1′ for key
- [ERROR] Fatal error: Can't open and lock privilege tables: Table 'mysql.host' doesn't exist
- R语言数据分析利器data.table包—数据框结构处理精讲
- SAP Fiori OData gateway 和后台 ABAP 系统的双缓存表(cache table)设计
- How to create a CDS redirect view for a given database table
- Application log save debug - how log data is persisted to database table
- Buffer table CRMD_DHR_HSRVORD
- GUID_COMP and GUID_COMPC - IBASE table
- SAP CRM one order Appointment table
- table 中的td 字段超长,超过部分用....表示
- 【Codeforces 448D】Multiplication Table
- 【codeforces 509A】Maximum in Table
- when click one item in table Select at least one column to perform the search
- C. Arthur and Table(Codeforces Round #311 (Div. 2) 贪心)
- table 中的tr 行点击 变换颜色背景