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

问题描述

元宵佳节，一场别开生面的灯笼大赛热闹非凡。NN 位技艺精湛的灯笼师依次落座，每位师傅都有相应的资历值，其中第 ii 位师傅的资历值为 AiAi​。从左到右，师傅们的资历值逐级递增（即 A1<A2<⋯<ANA1​<A2​<⋯<AN​）。同时，每位师傅都带来了自己精心制作的灯笼，其亮度值依次为 B1,B2,⋯ ,BNB1​,B2​,⋯,BN​。

大赛中，主持人会选择一个区间 [L,R][L,R]（1≤L<R≤N1≤L<R≤N），让这个区间内的师傅们进行两两比拼，构成一场“灯笼大乱斗”。

比拼规则如下：假设在区间 [L,R][L,R] 中，由师傅 ii 和师傅 jj（L≤i<j≤RL≤i<j≤R）进行对决。对决双方分别持有自己的灯笼。

如果师傅 ii 的灯笼亮度 BiBi​ 小于师傅 jj 的灯笼亮度 BjBj​，则双方交换灯笼（相应地，如果 Bi≥BjBi​≥Bj​，则不交换）。双方最终的得分计算方式为：资历值 + 持有灯笼的亮度。得分高者获胜，得分相同则平局。

由于在比赛中，资历深的师傅输给资历浅的师傅，将会有损颜面。因此，为了避免这种情况发生，主持人需要选择必胜区间。

必胜区间定义：如果一个区间内任意两位师傅进行比赛，资历值高的师傅都必定能够获胜，则称该区间为必胜区间。

现在，请你帮主持人算算，必胜区间共有多少个？

输入格式

第一行包含一个整数 NN (1≤N≤105)(1≤N≤105)，表示灯笼师傅的数量。

第二行包含 NN 个整数 A1,A2,…,ANA1​,A2​,…,AN​ (1≤Ai≤109)(1≤Ai​≤109)，表示每位师傅的资历值，满足 A1<A2<⋯<ANA1​<A2​<⋯<AN​。

第三行包含 NN 个整数 B1,B2,…,BNB1​,B2​,…,BN​ (1≤Bi≤109)(1≤Bi​≤109)，表示每位师傅的灯笼亮度值。

输出格式

输出一个整数，表示必胜区间的总数量。

样例输入 3 1 3 5 3 4 1

样例输出 1

 [L,R]必胜，只需要看R+1和R的关系就好了，如果R+1能赢R，则R+1必胜[L,R]

具体证明不会

#include <iostream> using namespace std; int main() { int n; cin>>n; int an[n], bn[n], cn[n]; for(int i=0; i<n; i++){ cin>>an[i]; } for(int i=0; i<n; i++){ cin>>bn[i]; } long long int num = 1, res = 0; for(int i=1; i<n; i++){ if(bn[i] > bn[i-1]){ if(an[i] - bn[i] > an[i-1] - bn[i-1]){ res += num; ++num; } else{ num = 1; } } else{ if(an[i] + bn[i] > an[i-1] + bn[i-1]){ res += num; ++num; } else{ num = 1; } } } cout<< res; return 0; }

结果res类型必须为longlongint ，int是不行的