谎牛计数（春季每日一题 53）

谎牛计数（春季每日一题 53）

奶牛 Bessie 躲在数轴上的某处。

不幸的是，可能不存在躲藏位置与所有奶牛的回答均一致，这意味着并非所有奶牛都在说真话。

计算在撒谎的奶牛的最小数量。

输出格式 输出在撒谎的奶牛的最小数量。

输入样例1：

2G 3L 5

输出样例1：

0

样例1解释 有可能没有奶牛在撒谎。

输入样例2：

2G 3L 2

输出样例2：

1

样例2解释 至少一头奶牛在撒谎。

// 枚举每一个端点，撒谎的牛的数量等于左边的 L 之和 + 右边的 G 之和// Bessie 所在位置取端点中间和取端点对答案的影响是一样的#include#include#define x first#define y secondusing namespace std;const int N = 1010;int n;pair 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。