问题描述
Given n elements, which have two properties, say Property A and Property B. For convenience, we use two integers Ai
and Bi
to measure the two properties.
Your task is, to partition the element into two sets, say Set A and Set B , which minimizes the value of max(x∈Set
A) {Ax}+max(y∈Set
B) {By}.
See sample test cases for further details.
输入
There are multiple test cases, the first line of input contains an integer denoting the number of test cases.
For each test case, the first line contains an integer N, indicates the number of elements. (1 <= N <= 100000)
For the next N lines, every line contains two integers Ai and Bi indicate the Property A and Property B of the ith element. (0 <= Ai, Bi <= 1000000000)
输出
For each test cases, output the minimum value.
样例输入
1
3
1 100
2 100
3 1
样例输出
Case 1: 3
题意:找出一个最大的和最小,
思路:先排序,然后枚举即可,,
AC代码:
#include<iostream>
#include<string.h>
#include<cstdio>
#include<memory.h>
#include<algorithm>
#include<vector>
#define N 100005
using namespace std;
typedef struct node
{
__int64 x;
__int64 y;
}Node;
Node s1[N];
bool cmp2(Node xx,Node yy)
{
return xx.y>yy.y;
}
int main()
{
int T;
scanf("%d",&T);
for(int k=1;k<=T;++k)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%I64d%I64d",&s1[i].x,&s1[i].y);
sort(s1,s1+n,cmp2);
__int64 minx=s1[0].y;
__int64 p=-1;
for(int i=1;i<n;++i)
{
if(s1[i-1].x>p) p=s1[i-1].x;
s1[i].y+=p;
if(s1[i].y<minx) minx=s1[i].y;
}printf("Case %d: %I64d\n",k,minx);
}return 0;
}
基本信息
#: 7214
题目: 1198
提交人: pursuit
语言: G++
提交时间 2012-07-14 09:34:28
分享到:
相关推荐
软件支持从2014年12月改版后的百度指数,批量采集百度指数的整体指数,移动指数,导出从2011年开始的每天的整体指数,移动指数数据...百度网盘:链接:https://pan.baidu.com/s/16U4cyiQzwPEpENSYiwMpwQ 提取码:y460
java连接mysql数据库的驱动,里边包含两个版本:5.1.47、8.0.28 也可从以下两个地址免费下载: ...3. https://cdn.mysql.com//archives/mysql-connector-java-5.1/mysql-connector-java-5.1.47.zip
[{"url":"http://192.168.0.104:8080/app-debug.apk","versionCode":5,"versionName":"1.4.20161008","updateMessage":"版本更新为4"}]
HeyUI UI组件库。组件文献资料访问 。安装npm install heyui -- save开始基本的< script src =" https://cdn.jsdelivr.net/npm/vue " > </ script ><... </ script >...基本在线演示高级import Vue ...
1、下载安装Foxit PhantomPDF Business 5(福昕PDF电子文档处理套件企业版),...http://cdn01.foxitsoftware.com/pub/foxit/phantomPDF/desktop/win/5.x/5.0/chs/FoxitPhantomPDF504_Business_chs_Setup.msi 64位: ...
做tc升级时用到,找了很久... <link crossorigin="anonymous" media="all" integrity="sha512-lLo2nlsdl+bHLu6PGvC2j3wfP45RnK4wKQLiPnCDcuXfU38AiD+JCdMywnF3WbJC1jaxe3lAI6AM4uJuMFBLEw==" rel="stylesheet" href=...
阿里云视频点播转码SDK,文档地址https://helpcdn.aliyun.com/product/29932.html?spm=a2c4g.11186623.6.540.57403893NeEgPt
官方下载地址:http://cdn07.foxitsoftware.cn/pub/foxit/phantomPDF/desktop/win/8.x/8.3/zh_cn/FoxitPDFEditor8.3.0.14878_ZH_Setup.msi。 本文包含两个文件:FoxitPDFEditor8.3.0.14878_ZH_Setup.msi(最新福昕...
(更多说明请到网站查看http://www.86y.org/art_detail.aspx?id=831) 1、运行环境需要framework 4.5.2开发版 有328M的大小。需要去下载并安装。(如果已经有这个版本的framework就不需要再安装了); 2、本人使用的...
"logo": "http://cdn.ickd.cn/mobile/images/logos/a2u.png", "website": "http://www.a2u.com.au/", "tel": "03 98774330/04 04616906", "inland": true }, { "code": "aae", "name": "AAE快递", "logo": ...
\\__.-"-._____ \\__.-"-._____ \\__.-"-._____ '-(_)---(_)--` \\__.-"-._____ .....'-(_)---(_)--` ... 'https://cdn1.com/img.png' , 'https://cdn2.com/img.png' , 'https://cdn3.com/img.png' ] ; race
手机扫描二维码访问移动端网页,网页判断你用的是安卓手机还是苹果手机,从而下载不同的app.zip 手机扫描二维码打开手机网页,网页判断你用的是android手机还是iphone手机,从而去不同的地方下载app
提供类似teamviewer的远程协助功能,它这个免费版本支持个人和商业使用(具体可以查看官方介绍:https://wayk.devolutions.net/compare)。 ...支持Windows、Linux、macOS,我这里提供了Windows和macOS的,其中Windows...
Extjs 5 beta 版下载链接:http://cdn.sencha.com/ext/beta/ext-5.0.0.736.zip Extjs 4.2.1 下载链接:http://cdn.sencha.com/ext/gpl/ext-4.2.1-gpl.zip Extjs 4.0.7 下载链接:http://cdn.sencha.
线刷工具下载:http://cdn.tvapk.com/zndsjc/burning_tool_v2.0.5.15-build9.zip 1、下载好线刷固件; 2、电脑端安装线刷工具USB_Burning_Tool,注意安装过程中会进行驱动预安装,不要跳过;安装完成后,运行工具;
script type =" text/javascript " src =" http://cdn.clappr.io/latest/clappr.min.js " > </ script > < script type =" text/javascript " src =" ...
网页制作中可以加入这些代码,提供本地影片作为qvod资源,别人浏览你的网页就可以使用qvod在线观看影片
MathFlare CDN 由 MathFlare Co. Ltd. 提供支持 关键文件 Bootstrap.js 和 Bootstrap.css https://cdn.mathflare.tk/bootstrap.min.css https://cdn.mathflare.tk/bootstrap-grid.min.css ...
腾讯的官方SDK,导入IDEA直接打开demo下的Demo类。直接就能运行,当然自己也可以重新建立demo。测试。
网上的API demo有一定错误, 我修复了这些错误,可以直接使用,这个是api18