codeforces D. Multiplication Table

http://codeforces.com/contest/448/problem/D

题意:一个n×m的矩阵,a[i][j]=i*j; 然后把a数组排序,找出第k个数。

思路:1-n×m二分枚举,然后统计比小于等于x的数的个数与k相比较。

 #include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 1000100
#define ll long long
using namespace std;
const int inf=<<; ll n,m,k;
ll a[maxn];
ll dp[][]; bool ok(ll x)
{
ll cnt=;
for(int i=; i<=n; i++)
{
cnt+=min(x/(ll)i,m);
}
if(cnt>=k) return true;
return false;
} int main()
{
cin>>n>>m>>k;
ll l=,r=n*m;
ll ans;
while(l<=r)
{
ll mid=(l+r)>>;
if(ok(mid))
{
ans=mid;
r=mid-;
}
else l=mid+;
}
cout<<ans<<endl;
return ;
}
上一篇:nginx1.8.1反向代理、负载均衡功能的实现


下一篇:HttpCookie