字首和+桶+map

提示：文章寫完後，目錄可以自動生成，如何生成可參考右邊的幫助文檔

文章目錄

• ​​前言​​
• ​​一、例如：​​
• ​​代碼如下​​

前言

當我們想對字首和進行标記的時候，有for和桶兩種方法，若使用for就得嵌套，達到O(n^2)的時間複雜度，在部分題目當中，很可能會逾時。

于是，我們便想到了用超快的桶排來進行标記，但桶排也是有局限性的，又大又多的資料很可能使所要标記的數超過數組的最大長度，這個時候，map便能解決這個關鍵性的問題。

一、例如：

描述

那是另一個世界，那個世界裡的老人們常常說天圓地方，在夜晚天空中散落着很多的星星。在這些星星中，如果某四顆星星相連能夠構成一個矩形，老人們給孩子們念叨着，這是“最美麗相遇”。

這天晚上hws和zyh，躺在軟軟的草地上，看着夜空中的星星（注意，今晚的星星隻會出現在圓形天空的圓周上！），hws對zyh說，我們的相遇一定是最美麗的相遇吧~

zyh點了點頭，睜大了他的眼睛，因為他想向hws證明他們的相遇一定是最美麗的相遇 – 他想要在夜空中尋找到所有不重複的“最美相遇”。

相信聰明的你也一定能找到吧~

輸入

第一行為正整數NN，表示夜空中星星的個數有N-1N−1個,将天空分成了NN段圓弧，接下來NN行順時針給出這NN段圓弧的長度l。

以上各值都為正整數。

輸出

輸出一個整數KK，表示夜空中所有不重複的“最美相遇”的個數。

注意，在那個世界裡，00是最大的數，是以當夜空中的“最美相遇”個數為00。

代碼如下

#include<bits/stdc++.h>
using namespace std;
#define N 1000000
double a[N];
 map<double,long long>b;
int main()
{
  
  int n;
  double c=0;
  scanf("%lld",&n);
  for(int i=1;i<=n;i++)
  {
    double q;
    scanf("%lf",&q);
    a[i]=a[i-1]+q;
    b[a[i]]=1;
  }
  
  c=a[n]*1.0/2;
  
  long long cont=0;
  for(int i=1;i<=n;i++)
  { 
      if(b[a[i]+c])
      {
        cont++;
      }
    
  }

   if(cont<=1)
   {
    printf("Lovers get married!\n");
   }
   else
   {
    printf("%lld\n",cont*(cont-1)/2);
   }
  return 0;
}