题解P2969

Zhengsiwei · 2020-02-13 20:52:38 · 题解

题解P2969 音符 Music Notes

这是题目链接。
注： “在时间段区间t，T+1内，奶牛敲的是哪个音阶？”意思是说，输入数字 T，输出时刻 T 奶牛正在演奏哪个音阶。

下面是解题部分。如果你希望能立刻得到正解，请跳过“思路1”。

• 思路1 ：
  所用算法：模拟（我不确定）。
  枚举所有音阶，直到找到 T 所在的音阶。 优缺点：

  • 优点：思路易想，易理解。代码简短。
  • 缺点：会超时。本题中，不算输入，Q 次查询，每次将音阶数组扫一遍，时间复杂度 O(N)，总时间复杂度 O(QN)，这个时间复杂度是不能被接受的。

• 思路2 ： 所用算法：前缀和、二分。
  算法讲解（可跳过）：
  前缀和。设某数组为 a,则建立一个数组 pre，pre(i)=\sum_{n=0}^{i}a\left(i\right)=a(0)+a(1)+a(2)...+a(i)。前缀和主要用于求和（a(i)+a(i+1)+...+a(j-1)+a(j)=\sum_{n=i}^{j}a\left(n\right)=pre(j)-pre(i-1)），不过这次它是用来记录音阶结束时刻的。前缀和数组生成代码：

  int pre[50100]={0};
  
  pre[0]=a[0];
  for(int i=1;i<=n;i++)
      pre[i]=pre[i-1]+a[i];

  二分。仅可用于有序序列。时间复杂度是 check 函数的时间复杂度乘以 \log n。详情你可以参考它。代码：

  int Binary(int start/*查找起始点*/,int end/*查找结束点*/, .../*此处填其余必要变量*/){
      int ans,mid;
      while(start<=end){
          mid=(start+end)/2;
          if(check(mid)/*check函数返回mid是否合法，合法返回 true，否则返回 false*/){
              ans=mid;
              end=mid-1;
          }
          else
              start=mid+1;
      }
      return ans;
  }

  言归正传。我们可以用前缀和储存音阶结束时刻，然后用二分算法找到答案。 优缺点：

  • 优点：时间复杂度低！本题中，不算输入，Q 次查询，check() 是 O(1) 的，总时间复杂度 O(Q \log N),稳得很。
  • 缺点：？？

下面是我的代码。代码中有注释，希望你可以看懂！欢迎参考。

//时间复杂度：O(Q log N)
//空间复杂度：O(N)
#include <bits/stdc++.h>
using namespace std;
int Binary_Search(int array[]/*待查找数组*/,int start/*查找起始点*/,int end/*查找结束点*/,int key/*键值*/){
    int ans,mid;
    while(start<=end){
        mid=(start+end)/2;
        if(array[mid]-1>key){
            ans=mid;
            end=mid-1;
        }
        else
            start=mid+1;
    }
    return ans;
}//二分查找非递归版，我没有用STL
int n,q,b[50100]/*变量名如题意*/,pre[50100]/*pre——前缀和*/,temp/*一个临时变量*/;
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>b[i];
        pre[i]=pre[i-1]+b[i];/*处理前缀和*/
    }/*输入数据*/
    for(int i=0;i<q;i++){
        cin>>temp;
        cout<<Binary_Search(pre,1,n,temp)<<endl;
    }/*回答询问*/
    return 0;
}

照例给一个提交记录。
欢迎提出意见。如有意见，请在评论区@我，或私信我。我会尽量作出回应（只是不保证回应速度）。