牛客小白月赛16 小石的妹子 (贪心 )

el/2024/6/24 18:51:10

链接:https://ac.nowcoder.com/acm/contest/949/F
来源:牛客网
 

小石的妹子

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

小石有 n 个妹子,每个妹子都有一个细心程度 aia_iai​ 和一个热心程度 bib_ibi​,
小石想给她们一个重要程度 tit_iti​(重要程度为 1 表示最重要,重要程度越小表示越重要)。
如果一个妹子 i 的细心程度和热心程度都比妹子 j 大,那么妹子 i 的重要程度要大于妹子 j 的重要程度,即妹子 i 比妹子 j 重要。
流程如下:
每次从所有没有重要程度的妹子中,找到若干妹子。对于这些妹子的任意一个,需要保证没有其他妹子比她更重要。然后把她们的重要程度标为 1 。下一次再从剩下没有重要程度的妹子中找到若干妹子,依然符合上述条件,然后把她们的重要程度标为 2,……,重复直到所有妹子都有自己的重要程度。
由于妹子太多,小石忙不过来,请你帮帮他。

输入描述:

第一行输入一个正整数 n,表示妹子的数量。
接下来 n 行,每行两个正整数 ai,bia_i,b_iai​,bi​,描述每个妹子的细心程度和热心程度。 
保证所有的 aia_iai​ 两两不等,所有的 bib_ibi​ 两两不等。 

输出描述:

共 n 行,第 i 行输出一个正整数 tit_iti​ 表示第 i 个妹子的重要程度。

示例1

输入

复制

5
1 4
2 2
3 3
4 1
5 5

输出

复制

2
3
2
2
1

说明

第一轮取第 5 个妹子(5 5),因为没有其他妹子比她重要,标记为 1;第二轮取编号为 1,3,4 的妹子,因为对于其中的任意一个妹子,都没有其他妹子比她们重要,标记为 2;第三轮把编号为 2 的妹子标记为 3 。

备注:

1≤n≤105,1≤ai,bi≤1091 \leq n \leq 10^5,1 \leq a_i,b_i \leq 10^91≤n≤105,1≤ai​,bi​≤109

#include<bits/stdc++.h>
using namespace std;const int M = 100005;int rnk[M];
struct node 
{int id, x;bool operator < (const node &t) const{return x > t.x;}
}a[M], b[M];int main()
{int n, k = 0;cin >> n;for( int i = 0; i < n; i++ ){cin >> a[i].x >> b[i].x;a[i].id = i;}sort( a, a+n ); for( int i = 0; i < n; i++ )if( rnk[a[i].id] == 0 ){rnk[a[i].id] = ++k;int now = b[a[i].id].x;for( int j = i+1; j < n; j++ )if( rnk[a[j].id] == 0 && b[a[j].id].x > now ){rnk[a[j].id] = k;now = b[a[j].id].x;}} for( int i = 0; i < n; i++ )cout << rnk[i] << endl;return 0;
}

 


http://www.ngui.cc/el/3419479.html

相关文章

牛客 回文数(模拟 )

链接&#xff1a;https://ac.nowcoder.com/acm/contest/1071/A 来源&#xff1a;牛客网 题目描述 今年是国际数学联盟确定的“2000——世界数学年”&#xff0c;又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛&#xff0c;组织了一场别开生面的数学…

牛客Game with numbers(暴力)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/942/B 来源&#xff1a;牛客网 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 给定大小为n{n}n的集合S{S}S 一…

Andrew算法——凸包问题

Andnew算法是Graham扫描法的变种 步骤&#xff1a; 把所有点优先按照横坐标x从小到大排序&#xff0c;如果x坐标相等&#xff0c;则按照y坐标从小到大排序去除重复的点&#xff0c;&#xff08;unique函数好评&#xff09;从左到右扫描下凸包&#xff0c;把满足条件的点放入b…

hdu 6546 Function(贪心+堆优化)

Function Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 278 Accepted Submission(s): 106 Problem Description wls 有 n 个二次函数 Fi (x ) ai x2 bi x ci (1 ≤ i ≤ n ). 现在他想在∑ni1 xi m …

结构体重载输入输出运算符

可以直接输入结构体&#xff0c;顺便初始化&#xff1b; #include<bits/stdc.h> using namespace std;struct node {int x, y, z;friend istream & operator >> (istream&, node &t){cin >> t.x >> t.y;t.z 1; //顺便初始化z return cin…

牛客训练哈希专题-矩阵 ( 哈希+二分 )

链接&#xff1a;https://ac.nowcoder.com/acm/problem/13610 来源&#xff1a;牛客网 矩阵 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 131072K&#xff0c;其他语言262144K 64bit IO Format: %lld 题目描述 给出一个n * m的矩阵。让…

Fancy Signal Translate(思维)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/16/D 来源&#xff1a;牛客网 Fancy Signal Translate 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 131072K&#xff0c;其他语言262144K 64bit IO Format: %lld 题目描述 FST是一…

hdu 1263 水果 (map)

水果 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 15438 Accepted Submission(s): 5999 Problem Description 夏天来了~~好开心啊,呵呵,好多好多水果~~ Joe经营着一个不大的水果店.他认为生存之道就是…

hdu4525 威威猫系列故事——吃鸡腿(坑人的题目)

威威猫系列故事——吃鸡腿 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 3363 Accepted Submission(s): 736 Problem Description 威威猫不是一只普通的猫&#xff0c;普通的猫喜欢吃鱼&#xff0c;但威…

2299:Ultra-QuickSort ( 树状数组 求逆序对 )

题目来源&#xff1a;http://bailian.openjudge.cn/practice/2299?langen_US Ultra-QuickSort 查看提交统计提示提问 总时间限制: 7000ms 内存限制: 65536kB 描述 In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a s…