音乐节拍【模拟】

　

音乐节拍

题目大意：

---

思路：

几万的范围，O(n2)" role="presentation">O(n2)$O(n^2)$肯定过不了，但O(nlogn)" role="presentation">O(nlogn)$O(nlogn)$可以过。

我们可以使用离线做法，将问题排序，再用指针j" role="presentation">j$j$指向每一个问题，由于这时问题满足单调递增，所以总共就只要O(n)" role="presentation">O(n)$O(n)$，平均每次循环O(1)" role="presentation">O(1)$O(1)$,再加上枚举的大循环，求出答案就只要O(n)" role="presentation">O(n)$O(n)$所以这样做总时间复杂度为O(nlogn)" role="presentation">O(nlogn)$O(nlogn)$。

当然这道题还可以用二分，时间复杂度O(qlogn)" role="presentation">O(qlogn)$O(qlogn)$。

---

代码：

#include <cstdio>
#include <iOStream>
#include <algorithm>
using namespace std;

int n,m,a[80001],j;

struct N
{
    int num,q,ans;
}b[80001];

bool cmp(N x,N y)
{
    return x.q<y.q;
}

bool cmp2(N x,N y)
{
    return x.num<y.num;
}

int main()
{
    freopen("mnotes.in","r",stdin);
    freopen("mnotes.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]+=a[i-1];  //前缀和
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&b[i].q);
        b[i].num=i;
    } 
    sort(b+1,b+m+1,cmp);  //排序
    j=1;  //指针
    for (int i=1;i<=n;i++)
    {
        while (b[j].q<a[i])  //单调性
        {
            b[j].ans=i;
            j++;
            if (j>m) break;
        }   
        if (j>m) break;
    }
    sort(b+1,b+m+1,cmp2);  //排回去
    for (int i=1;i<=m;i++)
     printf("%d\n",b[i].ans);
    return 0;
}

相关阅读

APP点评：「网易云音乐」APP分析

网易云音乐是一款需求满意度、效率性能、系统活性都较高的，有一定实力，但面临较大压力（包括短用户和竞品）的互联网产品。现在，我们一起

在Rhythmbox里添加音乐电台

在Rhythmbox里添加音乐电台  http://zhouzhengji2005.blog.163.com/blog/static/120278722012822111630/http://zhangjun06080.

【强烈推荐】一个非常好用的音乐下载网站（可下载音乐到

【强烈推荐】一个非常好用的音乐下载网站（可下载音乐到手机） 进入大版权时代以来，仅在一个app上找到所有歌曲的时代已经一去不返了

如何打造自家产品2018年的“年终盘点”？——以网易云音

支付宝年度账单、网易云音乐年度盘点，基本上每年都会刷一遍朋友圈。除开本身产品之外，在运营和营销方面，有多少是可以学习的呢？17年末

新物种的机会：强敌环饲，网易云音乐在下半场是如何突围？

对于小团队或者小公司来说，很难有大的突破机会。但如有做出好产品的基因。在格局已定，强敌环饲的情况下，也有突围的可能。一、下半场