admin管理员组文章数量:1558087
题目描述
Measuring the area of a certain shape is an important part of certain geometric problems.
For a point A(x,y) on the plane, we define the F(x,y) as ∣x∣∗∣y∣,which means the area of the rectangle with the vertex(x,0),(0,y),(0,0),(x,y).
You are given n∗m vertex with integral coordinates in the form of (i,j),and 1≤i≤n,1≤j≤m. You need to find the K-th biggest value of F(i,j),when 1≤i≤n,1≤j≤m.
It’s guranteed that K≤n∗m.
输入描述:
Three integers n,m,Kn,m,K_{}n,m,K(1≤n,m,K≤1061\leq n,m,K\leq 10^61≤n,m,K≤106).
输出描述:
One integer,the K-th biggest value of F(i,j)F(i,j)_{}F(i,j).
示例1
输入
3 3 4
输出
4
说明
In this eaxmple, the values of all F(i,j) are 1,2,2,3,3,4,6,6,9.
So the 4-th biggest value of F(i,j)F(i,j)_{}F(i,j) is 4.
题目大意:
输入两个数n,m,k.得到从1-n 分别乘以 1-m的数.然后排列输出第K大的数
解题思路:
声明:这是看了别的大佬的做法后自己仿造的.如有侵犯请联系我删除.
利用set容器中pair中一个记录最大值,另外一个是产生最大值的数.然后最大值减去这个数再插入回容器.set容器根据值的大小排序,所以顶上一直是最大值,减一次就会产生第二大的数.以此类推可以产生排在第几的数.
限制
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
代码:
#include<iostream>
#include<set>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair < ll, ll> pll;
set<pll> pg;
int main()
{
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i <= n; ++i)
{
pg.insert(pg.begin(),{ i * m,i });
}
k--;
while (k--)
{
set<pll>::iterator it = pg.end();
it--;
ll val = it->first;
ll line = it->second;
pg.insert(pg.end(),{ val - line,line });
pg.erase(it);
}
set<pll>::iterator it = --pg.end();
cout << it->first << endl;
return 0;
}
运行结果
本文标签: GPCPC01AnEasyProblem
版权声明:本文标题:GPCPC_01_An_Easy_Problem 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1727341211a1109431.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论