F.快快乐乐剪羊毛

题目移动草地，本人移动的羊，相对关系对结果不影响

初始令羊全部位于草地左侧，将羊逐步向右移动，记录所有总价值。

可以发现移动过程中，只有出现某只羊移动到了新的草地时，总价值才会出现变化。

由此每次移动产生这一变化的最小距离，直到所有的羊在草地右侧。

初步暴力（时间超时）

#include<set>
using namespace std;
const int N=1e5+10,M=1e5+10;
typedef long long int ll;
ll n,m;
ll w[N];
ll s[N];//对w取前缀和 s[i]表示第i片草地的右边界
ll v[N];
ll x[M];
set<ll>ans;//set自带去重.size()代表元素个数，恰可以用于记录总价值数量
ll u[N];//u[i] 表示第i只羊在第u[i]片草地
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>w[i];
        s[i]=s[i-1]+w[i];
    }
    for(int i=1;i<=n;++i){
        cin>>v[i];
    }
    for(int i=1;i<=m;++i){
        cin>>x[i];
    }
    ll q=-s[n];//初始偏移量 使羊全部位于草地左侧
    ll res;//临时变量 不同位置含义不同
    do{
        res=0x3f3f3f3f;//此处代表移动最小距离
        for(int i=1;i<=m;++i){
            if(u[i]<=n)res=min(s[u[i]]+1-(q+x[i]),res);//到了草地外后移动无价值
        }
        if(res==0x3f3f3f3f)break;//所有羊在草地外 结束移动
        q+=res;//完成偏移
        res=0;//此处此时作为总价值
        for(int i=1;i<=m;++i){
            if(q+x[i]>s[u[i]])u[i]++;//更新位置
            res+=v[u[i]];//价值累加
        }
        ans.insert(res);//放入答案集
    }while(1);
    cout<<ans.size();
}

可以发现时间复杂度是移动次数*m，移动次数最大为任意羊位于任意操场起点的情况数量及nm

及时间复杂度O(nmm)，最坏m=1e5、n=1，时间复杂度1e10。

优化：

nm的移动次数我没能发现优化方式，加上给出了nm<=1e5，有充分理由认为这是最优时不能优化的部分

那就只能优化循环内部的找最小移动距离和求总价值

经验上在线维护最小使用优先队列时间复杂度log m

若队列元素为每只羊到下一片草地的移动距离，每次移动后所有距离需要减去最小移动距离，时间上不允许进行这种费时的操作，

但其他减可以用当前加代替，使用lp记录移动过的距离，队列元素为到下一片草地的距离+lp

每次移动只更新到达下一片草地的羊(因为是最小移动所有其实是队列元素值相同的羊)提供的价值来维护总价值

又发现到达下一片草地的距离+lp 就是下一片草地的左边界-初始位置就不需要用lp了

代码如下

#include<set>
#include<queue>
using namespace std;
const int N=1e5+10,M=1e5+10;
typedef long long int ll;
typedef pair<ll,ll>pll;
ll n,m;
ll w[N];
ll s[N];
ll v[N];
ll x[M];
set<ll>ans;
ll u[N];
priority_queue<pll,vector<pll>,greater<pll>>q;//小根堆 元素pll的first是下一片草地的左边界-初始位置 second代表第几只羊及羊的下标
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>w[i];
        s[i]=s[i-1]+w[i];
    }
    for(int i=1;i<=n;++i){
        cin>>v[i];
    }
    for(int i=1;i<=m;++i){
        cin>>x[i];
    }
    ll qp=-s[n];

    for(ll i=1;i<=m;++i){//将m只羊的数据放入小根堆
        ll l=s[u[i]]+1-(qp+x[i]);
        q.push({l,i});
    }

    ll res=0;//初始所有羊在草地左侧 总价值为0
    do{
        ll p=q.top().first;//取最小值
        while(q.size()&&p==q.top().first){//队列不空并元素值相等
            ll i=q.top().second;
            
            //更新总价值及羊的位置
            res-=v[u[i]];
            u[i]++;
            res+=v[u[i]];
            if(u[i]<=n)q.push({s[u[i]]+1-(qp+x[i]),i});//没有出草地右边界就继续放入队列
            q.pop();
        }
        ans.insert(res);
    }while(q.size());
    cout<<ans.size();
}