📆Date: 2023年1月5日
🎬Author: 小 y 同 学
📃Classify: 蓝桥杯每日一练
🔖Language: Python

🍀题目描述

• 题意
    给你一个长度为n的序列，请输出满足以下条件的$(i,j)$的数量
    $①1\le i\le j\le n②\min (a_i,a_j)=i③\max (a_i,a_j)=j$

• 输入格式
    第一行一个正整数$n(2\le n\le 5\times 10^5)$
    第二行包含n个正整数$a_i(1\le a_i\le n)$

• 输出格式
    一个正整数表示答案

• 样例输入1

4
1 3 2 4

• 样例输出1

2

• 样例输入2

10
5 8 2 2 1 6 7 2 9 10

• 样例输出2

8

🌿解题思路

• 题目梳理
    首先我们需要明白的是$(i,j)$要同时满足题目所说的三个条件才可以满足样例；知道一点以后我们可以在满足条件$①1\le i\le j\le n$的情况下讨论同时满足条件$②\min (a_i,a_j)=i③\max (a_i,a_j)=j$的情况，无非两种：$①a_i=i,a_j=j$或者$②a_i=j,a_j=i$我们可以分别计算这两种情况的数量相加即可得到结果。
• 数据输入
    n的输入很简单，注意转为int类型方便计算即可；对a_i的存储小y是先将数据num_li = list(map(int, input().split()))存入num_li列表中，再在列表的最前端插入一个0元素，因为列表下标是从0开始的，而i的计算是从1开始的，这里为了减少不必要的以外麻烦，就采取这种数据的整理模式。
• 核心处理
    对于上述第二种情况的处理非常简单判断此条件i == num_li[tem] and i < tem是否成立即可：这里的tem指的是a_i的值同时也是满足条件对应j的值，那么num_li[tem]就对应的a_j，同时应该注意满足条件$①1\le i\le j\le n$
    对于上述第一种情况则较为复杂，我们可以这么思考：如果a_i=i满足，那么与之配对的只有a_j=j，我们可以将所有的类似a_k=k的元素都作一个计数x_1；如果最终x_1==5，这里就举一个简单的例子1 2 3 4 5我们可以列举所有的满足情况①的情况：1 2,1 3,1 4,1 5,2 3,2 4,2 5,3 4,3 5,4 5，我们可以找到满足条件①的最终数量$s1=(x\_1-1)+...+3+2+1$也就是前$x\_1-1$的和，用前n项和公式$S=\frac{(1+n)\times n}{2}$计算即可，这里注意$n=x\_1-1$。

🌸Python源码

# _*_coding:utf-8_*_
# created by cy on 2023/1/5

def solve():
   n = int(input())
   num_li = list(map(int, input().split()))
   num_li.insert(0, 0)  # 列表的第一项插入0，使下标与i的值对应,注意列表长度n+1
   x_1 = 0  # 间接记录第一种情况
   x2 = 0  # 记录第二种情况

   for i in range(1, n + 1):
       tem = num_li[i]
       if tem == i:  # ai=i，aj=j间接的情况
           x_1 += 1
       elif i == num_li[tem] and i < tem:  # aj=i，ai=j的情况
           x2 += 1
   s = x2 + x_1 * (x_1 - 1) / 2
   print(int(s))


if __name__ == "__main__":
   solve()

📧Summary

  小y的今日一练到此画上了句号,欢迎友友们多给建议🌼🌼🌼
  有兴趣一起学习编程的小伙伴可以私聊小y一起学习,小y在Python,c/c++和matlab语言上均有一定的基础😜😜😜