[题解] P7954 [COCI2014-15#6] PAPRIKA

· · 题解

题目大意

  1. 每个辣椒有一个年龄 a_i 和想成为菜品 A 或 B 的梦想 b_i

  2. 用年龄不超过 x 的辣椒做菜品 A，用年龄超过 x 的辣椒做菜品 B。

  3. 相邻两个辣椒比较，a_i>a_j,b_i=1,b_j=0 时交换年龄。

  4. 问有多少个辣椒可以实现梦想。

分析

按照题意模拟即可。

读入 a_i 和 b_i，如果 i 不为 1，那么和前一个读入的比较。如果满足题目要求的交换条件则交换。

注意： 比较的时候要枚举哪一个辣椒年龄更大，不能只枚举一种情况。

经过一轮在线模拟交换后，再用一重循环判断有哪些达成了梦想。

Code：

#include <bits/stdc++.h>
using namespace std;
int n, x, s, a[1007], b[1007];
int main(){
    scanf ("%d%d", &n, &x);
    for (int i=1; i<=n; i++){
        scanf ("%d%d", &a[i], &b[i]);
        if (i == 1) continue;//i = 1时没法和前面的比较 
        if ((a[i] > a[i-1] && b[i] == 1 && b[i-1] == 0) || (a[i-1] > a[i] && b[i] == 0 && b[i-1] == 1)) //有两种情况 
        swap(a[i], a[i-1]);
    }
    for (int i=1; i<=n; i++){
        s += (a[i] <= x && b[i] == 1), s += (a[i] > x && b[i] == 0);//判断语句返回值为 1 或 0 
    }
    printf ("%d\n", s);
    return 0;
}