当前位置:网站首页>谎牛计数(春季每日一题 53)
谎牛计数(春季每日一题 53)
2022-07-07 14:28:00 【sweetheart7-7】
奶牛 Bessie 躲在数轴上的某处。
农夫约翰的 N N N 头奶牛中的每头奶牛都有一条信息要分享:第 i i i 头奶牛说 Bessie 躲在小于或等于 p i p_i pi 的某个位置,或者说 Bessie 躲在大于或等于 p i p_i pi 的某个位置。
不幸的是,可能不存在躲藏位置与所有奶牛的回答均一致,这意味着并非所有奶牛都在说真话。
计算在撒谎的奶牛的最小数量。
输入格式
输入的第一行包含 N N N。
以下 N N N 行每行包含字符 L
或 G
,之后是一个整数 p i p_i pi。L
表示第 i i i 头奶牛说 Bessie 的躲藏位置小于或等于 p i p_i pi,而 G
表示第 i i i 头奶牛说 Bessie 的躲藏位置大于或等于 p i p_i pi。
输出格式
输出在撒谎的奶牛的最小数量。
数据范围
1 ≤ N ≤ 1000 1≤N≤1000 1≤N≤1000,
0 ≤ p i ≤ 1 0 9 0≤pi≤10^9 0≤pi≤109。
输入样例1:
2
G 3
L 5
输出样例1:
0
样例1解释
有可能没有奶牛在撒谎。
输入样例2:
2
G 3
L 2
输出样例2:
1
样例2解释
至少一头奶牛在撒谎。
// 枚举每一个端点,撒谎的牛的数量等于左边的 L 之和 + 右边的 G 之和
// Bessie 所在位置取端点中间和取端点对答案的影响是一样的
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N = 1010;
int n;
pair<int, char> q[N];
int s[N];
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> q[i].y >> q[i].x;
sort(q + 1, q + 1 + n);
for(int i = 1; i <= n; i++){
s[i] = s[i - 1];
if(q[i].y == 'L') s[i]++;
}
int res = n;
for(int i = n, r = 0; i; i--){
int j = i, t = 0;
while(j && q[j].x == q[i].x){
if(q[j].y == 'G') t++;
j--;
}
res = min(res, s[j] + r);
r += t;
i = j + 1;
}
cout << res << endl;
return 0;
}
边栏推荐
- Prediction - Grey Prediction
- prometheus api删除某个指定job的所有数据
- URL和URI的关系
- 【DesignMode】代理模式(proxy pattern)
- Markdown formula editing tutorial
- What else can an ordinary person do besides working in a factory to make money?
- null == undefined
- How can laravel get the public path
- Leetcode-136- number that appears only once (solve with XOR)
- 水平垂直居中 方法 和兼容
猜你喜欢
[Android -- data storage] use SQLite to store data
Imitate the choice of enterprise wechat conference room
【DesignMode】外观模式 (facade patterns)
HAVE FUN | “飞船计划”活动最新进展
[vulnhub range] thales:1
95.(cesium篇)cesium动态单体化-3D建筑物(楼栋)
Personal notes of graphics (1)
Personal notes of graphics (2)
spark调优(三):持久化减少二次查询
Pycharm terminal enables virtual environment
随机推荐
laravel 是怎么做到运行 composer dump-autoload 不清空 classmap 映射关系的呢?
二叉搜索树(基操篇)
Three. JS series (3): porting shaders in shadertoy
"The" "PIP" "entry cannot be recognized as the name of a cmdlet, function, script file, or runnable program."
【Vulnhub靶场】THALES:1
1亿单身男女“在线相亲”,撑起130亿IPO
预测——灰色预测
Balanced binary tree (AVL)
What about the pointer in neural network C language
How to determine whether the checkbox in JS is selected
01tire+链式前向星+dfs+贪心练习题.1
2022 the 4th China (Jinan) International Smart elderly care industry exhibition, Shandong old age Expo
As an Android Developer programmer, Android advanced interview
OpenGL personal notes
PHP实现执行定时任务的几种思路详解
平衡二叉树(AVL)
Odoo集成Plausible埋码监控平台
模拟Servlet的本质
Personal notes of graphics (4)
面试题 01.02. 判定是否互为字符重排-辅助数组算法