蓝桥杯 灯笼大乱斗【算法赛】

题目形貌

元宵佳节，一场别开生面的灯笼大赛热闹非凡。NN 位武艺博识的灯笼师依次落座，每位师傅都有相应的资历值，此中第 ii 位师傅的资历值为 AiAi​。从左到右，师傅们的资历值逐级递增（即 A
1<A2<⋯<ANA
1​<A2​<⋯<AN​）。同时，每位师傅都带来了自己经心制作的灯笼，其亮度值依次为 B
1,B2,⋯ ,BNB
1​,B2​,⋯,BN​。
大赛中，主持人会选择一个区间 [L,R][L,R]（
1≤L<R≤N
1≤L<R≤N），让这个区间内的师傅们举行两两比拼，构成一场“灯笼大乱斗”。
比拼规则如下&#xff
1a;假设在区间 [L,R][L,R] 中，由师傅 ii 和师傅 jj（L≤i<j≤RL≤i<j≤R）举行对决。对决两边分别持有自己的灯笼。

• 如果师傅 ii 的灯笼亮度 BiBi​ 小于师傅 jj 的灯笼亮度 BjBj​，则两边交换灯笼（相应地，如果 Bi≥BjBi​≥Bj​，则不交换）。
  
• 两边终极的得分盘算方式为&#xff
  1a;资历值 + 持有灯笼的亮度。得分高者得胜，得分雷同则平手。
  

由于在比赛中，资历深的师傅输给资历浅的师傅，将会有损颜面。因此，为了克制这种环境发生，主持人须要选择必胜区间。
必胜区间界说&#xff
1a;如果一个区间内恣意两位师傅举行比赛，资历值高的师傅都肯定可以或许得胜，则称该区间为必胜区间。
如今，请你帮主持人算算，必胜区间共有多少个&#xff
1f;
输入格式

第一行包罗一个整数 NN (
1≤N≤
105)(
1≤N≤
105)，表现灯笼师傅的数目。
第二行包罗 NN 个整数 A
1,A2,…,ANA
1​,A2​,…,AN​ (
1≤Ai≤
109)(
1≤Ai​≤
109)，表现每位师傅的资历值，满意 A
1<A2<⋯<ANA
1​<A2​<⋯<AN​。
第三行包罗 NN 个整数 B
1,B2,…,BNB
1​,B2​,…,BN​ (
1≤Bi≤
109)(
1≤Bi​≤
109)，表现每位师傅的灯笼亮度值。
输特殊式

输出一个整数，表现必胜区间的总数目。
样例输入

2. 3
4. 1 3 5
5. 3 4
6. 1

复制代码

样例输出

2. 1

复制代码

 [L,R]必胜，只须要看R+
1和R的关系就好了，如果R+
1能赢R，则R+
1必胜[L,R]
具体证明不会

1. #include <iostream>using namespace std;int main(){  int n;  cin>>n;  int an[n], bn[n], cn[n];    for(int i&#6
2. 1;0; i<n; i++){    cin>>an[i];  }   for(int i&#6
3. 1;0; i<n; i++){    cin>>bn[i];  }     long long int num &#6
4. 1;
5. 1, res &#6
6. 1; 0;  for(int i&#6
7. 1;
8. 1; i<n; i++){      if(bn[i] > bn[i-
9. 1]){        if(an[i] - bn[i] > an[i-
10. 1] - bn[i-
11. 1]){          res +&#6
12. 1; num;          ++num;        }        else{          num &#6
13. 1;
14. 1;        }      }      else{        if(an[i] + bn[i] > an[i-
15. 1] + bn[i-
16. 1]){          res +&#6
17. 1; num;          ++num;        }        else{          num &#6
18. 1;
19. 1;        }      }  }  cout<< res;  return 0;}

复制代码

效果res范例必须为longlongint ，int是不可的

123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。