[基礎(chǔ)算法1 ] 朋友的數(shù)量
題目描述
?題目描述：
? ? ? ?很多幼兒園的小朋友到一起參加市里的聯(lián)歡晚會，排成了一個長隊，小朋友們排隊有點無聊了，東張西望。如果兩個小朋友之間的人都不比他們兩個高，他們就可以互相看到，于是他們就成為了一對好朋友。當(dāng)然如果兩個小朋友之間沒有其它小朋友，則他們也會是一對好朋友。現(xiàn)在，請你算一下一共有幾對好朋友。?
? ? ? 兩個小朋友甲和乙，(甲, 乙)和(乙, 甲)只能算一對好朋友。
輸入格式：
? ? ?第一行n，表示小朋友個數(shù)
? ? ?第二行n個正整數(shù)，表示小朋友的高度
輸出格式：
? ? ? 一個數(shù)字，表示好朋友的對數(shù)
樣例輸入?復(fù)制
4 5 1 3 4
樣例輸出?復(fù)制
5
提示
樣例1說明：(5, 1)、(5, 3)、(5, 4)、(1, 3)、(3, 4)，一共5對。
數(shù)據(jù)范圍：
?20%：n<=1000，高度不會重復(fù)
?40%：n<=10,000，高度有重復(fù)
?100%：n<=500,000，高度有重復(fù)
程序
#include <iostream>#include <algorithm>#include <stack>using namespace std;?
stack<int> st;int a[500005];int main(){????int n;????cin >> n;????for (int i = 1; i <= n; i++)????????cin >> a[i];????int ans(0);????for (int i = 1; i <= n; i++)????{????????int t(1);????????while (!st.empty() && a[st.top()] <= a[i])????????{????????????if (a[st.top()] == a[i])????????????????t++;????????????ans++;????????????st.pop();????????}????????if (!st.empty())????????????ans++;????????while (t--)????????????st.push(i);????}????cout << ans;????return 0;}標(biāo)簽：
