土豪我们做朋友吧(1091)
问题描述:
人都有缺钱的时候,缺钱的时候要是有个朋友肯帮助你,那将是一件非常幸福的事情。有N个人(编号为1到N),一开始他们互相都不认识,后来发生了M件事情,事情分为2个种类,1:A和B成为了朋友,并且A的所有朋友都成了B的朋友,B的所有朋友也都成了A的朋友。2:A缺钱了,请求帮助,他需要向他朋友中钱最多的请求帮助,若不止一位,选择编号最小的。
输入:
多组测试数据,每组第一行是整数N(2<=N<=100000),表示有N个人,第二行N个数据,依次表示每个人有多少钱,第三行是M(1<=M<=100000),表示发生了M个事件。接下来是M行,首先输入事件种类P(1或者2),然后是对应的两个或者一个整数A,B或者A。数据保证都在32位以内。
输出:
对于每一个事件2,输出A需要请求的人的编号,若没有人能够帮助他,输出"NO ONE CAN HELP!"。
样例输入
1 2 3
2 1
1 1 3
2 1
样例输出
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010 int n,m;
int a[N];
int f[N];
pair<int,int> mx[N]; //最大的值、人
pair<int,int> cx[N]; //次大的值、人
pair<int,int> tmp[]; bool cmp(pair<int,int> a,pair<int,int> b)
{
if(a.first!=b.first) return a.first>b.first;
return a.second<b.second;
}
void init()
{
for(int i=;i<=n;i++)
{
f[i]=i;
scanf("%d",&mx[i].first);
mx[i].second=i;
cx[i].first=-;
cx[i].second=-;
}
}
int Find(int x)
{
if(x!=f[x]) f[x]=Find(f[x]);
return f[x];
}
void UN(int x,int y)
{
x=Find(x);
y=Find(y);
if(x==y) return;
f[x]=y;
tmp[]=mx[x];tmp[]=cx[x];
tmp[]=mx[y];tmp[]=cx[y];
sort(tmp,tmp+,cmp);
mx[x]=mx[y]=tmp[];
cx[x]=cx[y]=tmp[];
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
scanf("%d",&m);
while(m--)
{
int op,a,b;
scanf("%d%d",&op,&a);
if(op==)
{
scanf("%d",&b);
UN(a,b);
}
else
{
b=Find(a);
if(mx[b].first!=- && mx[b].second!=a)
printf("%d\r\n",mx[b].second);
else if(cx[b].first!=-)
printf("%d\r\n",cx[b].second);
else
printf("NO ONE CAN HELP!\r\n");
}
}
}
return ;
}
[swustoj 1091] 土豪我们做朋友吧的更多相关文章
-
[Swust OJ 1091]--土豪我们做朋友吧(并查集,最值维护)
题目链接:http://acm.swust.edu.cn/problem/1091/ Time limit(ms): 1000 Memory limit(kb): 32768 人都有缺钱的时候,缺 ...
-
[1-3] 把时间当做朋友(李笑来)Chapter 3 【提高心智,和时间做朋友】 摘录
1. 精确感知时间 我有个朋友叫做时间.她跟我真可算作两小无猜,默默陪了二十多年我才开始真正认识她.她原本没有面孔,却因为我总是用文字为她拍照,而因此可以时常伴我左右.她原本无情,我却可以把她当作朋友 ...
-
【产品经理】产品经理不懂API接口是什么,怎么和程序员做朋友?
接口不是技术经理来写吗?没接过它,一脸不清楚地节奏 开放即共享,是互联网的一个重要属性和精神.它是一种服务模式,一个特殊的产品,目前较大规模的互联网企业都有自己的开放平台. 如果把自己局限为一个功能产 ...
-
西南科技大学第十届ACM程序设计竞赛题解
A.德州扑克 B. 我恨11(1089) 问题描述 11是一个孤独的数字,小明十分讨厌这个数字,因此如果哪个数字中出现了11或者该数字是11的倍数,他同样讨厌这个数字.现在问题来了,在闭区间[L,R] ...
-
【Itext】7步制作Itext5页眉页脚pdf实现第几页共几页
itext5页眉页脚工具类,实现page x of y 完美兼容各种格式大小文档A4/B5/B3,兼容各种文档格式自动计算页脚XY轴坐标 鉴于没人做的这么细致,自己就写了一个itext5页眉页脚工具类 ...
-
奇葩app大盘点,你知道几个
1.I'm Rich 这个App最奇葩.不仅奇葩,还无聊.炫富.浮夸,曾经荣耀一时的"劳资是土豪"应用,售价999.99美元,功能和它的简介一样粗暴,999美元买来的红钻石就是土豪 ...
-
解题:HEOI 2012 朋友圈
题面 因为$A$中只有奇偶性不同的人才能做朋友,所以A中只可能出0/1/2个人,分类讨论 然后$B$中求最大团,转成补图后正好是个二分图(不然就不用做了),求最大点独立集=总点数-最大匹配 我洛谷上交 ...
-
[1-1] 把时间当做朋友(李笑来)Chapter 1 【心智的力量】 摘录
今天开了读书笔记这一专题,主要是对自己今后读的书有一个小小的记录,也为解决自己读书多年的存在的一些习惯的问题. 打小就喜欢书,可能最早的书是家人买的看图识动物.还记得七八岁时见书摊上的书时赖着不走央求 ...
-
[1-5] 把时间当做朋友(李笑来)Chapter 5 【小心所谓成功学】 摘录
有一个事实非常简单,却令人难以接受.这世界上所有的资源并非平均分布在每一个人的身上,能够比较接近地表示这种分布情况的数学曲线叫做“正态分布曲线”(Normal Distribution Curve) ...
随机推荐
-
The AndroidManifest.xml File
manifest (船运的)载货清单 http://www.android-doc.com/guide/topics/manifest/manifest-intro.html Every applic ...
-
介绍50个 WordPress 动作挂钩
WordPress 之所以能成为世界上最受欢迎的网页内容管理系统,原因就在于它的高度灵活性和可塑性,而这种灵活性和可塑性正是由“挂钩”(Hooks)简洁宜用的结构所决定的.可以说,没有过滤挂钩(Fil ...
-
使用Xshell连接Ubuntu
使用Xshell连接Ubuntu Xshell是一个安全终端模拟软件,可以进行远程登录.我使用XShell的主要目的是在Windows环境下登录Linux终端进行编码,非常方便.本文简单介绍下它的使用 ...
-
[Log函数]C++log函数使用
先引入头文件#include<cmath> 以e为底:log(exp(n)) 以10为底:log10(n) 以m为底:log(n)/log(m)
-
ftp 上传和下载
ftp 下载 #!/bin/bash #auth liwei #date DATE=$(date -d today +%Y%m%d) #data files path SRCDIR=/home/web ...
-
lua相关的小知识
lua的特性 1. 轻量级:一标准的C语言编写原发开放,编译后仅仅100K,占用内存小: 2. 扩展性:Lua提供了非常已于使用的扩展口和机制: 3. 支持面向过程编程和函数式编程 lua的数据类型 ...
-
Linux添加系统环境变量
在Linux下使用源码安装软件的时候,通常只能在软件安装目录下使用该软件命令(使用yum命令安装的除外),这样太麻烦,我们希望全局使用,可以将软件安装路径添加到系统环境变量里. 添加环境变量有2种方法 ...
-
window.opener()方法
<!DOCTYPE html><html><head><meta charset="GBK"><title>菜鸟教程(r ...
-
从0开始做一个的Vue图片/ 文件选择(上传)组件[基础向]
原文:http://blog.csdn.net/sinat_17775997/article/details/58585142 之前用Vue做了一个基础的组件 vue-img-inputer ,下面就 ...
-
HDU1042N!大数的阶乘java模板
import java.math.BigInteger; import java.util.Scanner; public class Main{ public static void main(St ...