P7799 [COCI2015-2016#6] PIANINO 题解

· · 题解

思路

当然大模拟干过去

现实的来讲，这不可能，因为 -10^9 \le a_i \le 10^9 的限制摆在这里。

但是注意到，有很小的 n \le 10^6 存在，我们就想怎么通过遍历 a 数组完成计算。

在 a_i 和 a_1 之间，一定会有一个整数上升次数（增高音量，但要是增高音量次数小于降低次数，这个数为负数），命为 cnt，和一个差距（就是 a_i-a_1 这个值），命为 x。

这时，我们就能计算出一个值 k=\frac{x}{cnt} 为能正好做到弹准 a_i 的。

但是有两个特殊情况：

  1. cnt=0

    可以说明此音符在 x=0 的时候一定可以弹准，进行记录。

  2. \left \lfloor k \right \rfloor \ne k$ 或者 $|k| \ne k

    说明 k 违背了题目中非负整数的要求，这个音符不可能弹准,直接抬走

一边处理，一边用 map 进行统计（空间比直接开桶小）。之后在找到最大，和那些固定能弹出的加起来就是第一问的答案，而找出这个答案的下标 k 为第二问答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int a[1000005];
map <int,int> b;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }//输入
    int cnt=0,ans=1,maxx=0,k=1;//初始化
    for(int i=2;i<=n;i++)
    {
        if(a[i]>a[i-1])cnt++;
        if(a[i]<a[i-1])cnt--;//统计更改次数 
        if(!cnt)
        {
            if(a[1]==a[i])
            {
                ans++;
            }
            continue;
        }//得零时进行特判
        int x=(a[i]-a[1]);
        if((a[i]-a[1])%cnt)
        {
            continue;
        }//要是有余数（除出来是小数），那就抬走
        int t1=((a[i]-a[1])/cnt);
        b[((a[i]-a[1])/cnt)]++;//往map上统计
        if(b[((a[i]-a[1])/cnt)]>maxx&&k>=0)
        {
            maxx=b[((a[i]-a[1])/cnt)];
            k=((a[i]-a[1])/cnt);
        }//超过最大就更新
    }
    cout<<maxx+ans<<"\n"<<k;
    return 0;
}