题解：P12006 【MX-X10-T2】[LSOT-4] 网易云

· · 题解

思路

注意题目里需要我们计算的是总和，根据加法结合律和加法交换律，我们容易得到不管如何改变听歌顺序，每一首歌对于答案的贡献总是固定的，证明如下：

令 n 个数 a_1,a_2,a_3...a_n 是每一首歌可以提供的好听值，n-1 个数 s_1,s_2,s_3...s_{n-1} 与题意相同。我们考虑两种听歌方式。

1 3
4 3
3 3
2 3

不难得出 ans=3a_1+3a_4+3a_3+3a_3=3s_1+3s_3

1 2
3 1
4 2
2 3
1 1
3 2
4 1

当我们将得到的等式合并一下同类项，会惊奇的发现这和上一种情况相同。

那么这道题就很简单了，在输入时统计每一首歌听的总次数，最后在 O(n) 的复杂度里就可以算出答案，只需要特判一下是否有歌无法计算即可

code

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define LB lower_bound
#define UB upper_bound
using ll=long long;using db=double;
#define int long long
inline ll read(){
    ll f=1,x=0;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') f=-f;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(ll x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
int n,m;
int s[200001],a[200001],b[200001];
map<int,int> mp;
signed main(){
    int sum=0;
    n=read(),m=read();
    for(int i=1;i<=n-1;i++) s[i]=read();
    for(int i=1;i<=m;i++)   a[i]=read(),b[i]=read(),mp[a[i]]+=b[i];
    for(int i=1;i<=n-1;i++){
        sum+=s[i]*mp[i];
        mp[i+1]-=mp[i],mp[i]=0;
    }
    if(mp[n])   cout<<"Impossible";
    else    cout<<sum;
}