题目描述
厨师 Marin 准备用 �n 个辣椒制作菜品。
他决定用所有年龄不超过 �x 天的辣椒来制作菜品 A,用其他的所有辣椒制作菜品 B。
每个辣椒都有自己的梦想,它们知道自己想要成为 A 还是 B。
但它们不知道 �x 的值。为了最大化实现梦想的辣椒数量,它们会采取如下策略进行交换:
- 第 1 个辣椒与第 2 个辣椒比较年龄,然后第 2 个辣椒与第 3 个辣椒比较年龄,依此类推,直到第 �−1n−1 和第 �n 个辣椒比较年龄。
- 若当前比较二者的编号为 �,�i,j,其中当前年龄较大的辣椒想成为菜品 A,当前年龄较小的辣椒想成为菜品 B,则它们会交换年龄。[1][1]
求出这样操作后实现梦想的辣椒数量。
输入格式
第一行两个整数 �,�n,x。
接下来 �n 行,每行两个整数 ��,��ai,bi,分别表示第 �i 个辣椒的年龄与梦想。
- 若 ��=1bi=1,则表示第 �i 个辣椒想成为菜品 A。
- 若 ��=0bi=0,则表示第 �i 个辣椒想成为菜品 B。
根据这种定义,「题目描述」中 [1][1] 更加严谨的表述为:
两个辣椒 �,�i,j 会交换年龄当且仅当 ��>��ai>aj 且 ��=1bi=1 且 ��=0bj=0。
输出格式
仅一行一个整数,即实现梦想的辣椒数量。
输入输出样例
输入 #1
4 5 2 0 3 0 4 0 5 0
输出 #1
0
输入 #2
5 5 3 1 2 0 13 1 2 0 10 1
输出 #2
5
输入 #3
6 10 15 1 12 1 8 0 10 1 3 0 1 1
输出 #3
4
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=10001; 4 int n,x,res; 5 struct node 6 { 7 int a,b; 8 bool vis; 9 }l[N]; 10 int main() 11 { 12 cin>>n>>x; 13 for(int i=0;i<n;i++) cin>>l[i].a>>l[i].b; 14 for(int i=0;i<n-1;i++) 15 { 16 if(l[i].a<=x&&l[i].b==1&&!l[i].vis) res++,l[i].vis=true; 17 if(l[i].a>x&&l[i].b==0&&!l[i].vis) res++,l[i].vis=true; 18 if(l[i].a>x&&l[i].b==1&&!l[i].vis&&l[i+1].a<=x&&l[i+1].b==0&&!l[i+1].vis) 19 { 20 res+=2;l[i].vis=l[i+1].vis=true; 21 } 22 if(l[i].a<=x&&l[i].b==0&&!l[i].vis&&l[i+1].a>x&&l[i+1].b==1&&!l[i+1].vis) 23 { 24 res+=2;l[i].vis=l[i+1].vis=true; 25 } 26 } 27 if(l[n-1].a<=x&&l[n-1].b==1&&!l[n-1].vis) res++,l[n-1].vis=true; 28 if(l[n-1].a>x&&l[n-1].b==0&&!l[n-1].vis) res++,l[n-1].vis=true; 29 cout<<res<<endl; 30 return 0; 31 }