跳石头，搭梯子

C++(g++ 7.5.0) 解法, 执行用时: 82ms, 内存消耗: 5888K, 提交时间: 2023-06-23 21:43:48

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,h[N];
vector<int>a1,a2;
ll sum[N];
vector<ll>v;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=2;i<=n;i++){
		sum[i]=sum[i-1]+abs(h[i]-h[i-1]);
	}
	for(int i=1;i<=n;i++)
	if(a1.empty()||h[a1.back()]<=h[i]){
		a1.push_back(i);
	}
	for(int i=n;i>=a1.back()+1;i--){
	if(a2.empty()||h[a2.back()]<=h[i])
    a2.push_back(i);
	}
	while(!a2.empty()){
		a1.push_back(a2.back());
		a2.pop_back();
	}
	for(int i=1;i<a1.size();i++){
		ll flag=sum[a1[i]],bb=sum[a1[i-1]];
        v.push_back(flag-bb-abs(h[a1[i]]-h[a1[i-1]]));
	}
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	ll ans=sum[n];
	for(int i=0;i<min(m,(int)v.size());i++){
		ans-=v[i];
	}
	cout<<ans;
    return 0;
}

pypy3 解法, 执行用时: 203ms, 内存消耗: 47008K, 提交时间: 2023-06-12 11:16:25


if __name__ == "__main__":
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    pre = [0] * n 
    
    for i in range(1, n):
        pre[i] = pre[i-1] + abs(h[i] - h[i-1])
    
    st1, st2 = [], []
    for i in range(n):
        if not st1 or h[st1[-1]] <= h[i]:
            st1.append(i)
    for i in range(n-1, st1[-1], -1):
        if not st2 or h[st2[-1]] <= h[i]:
            st2.append(i)
    st2 = list(reversed(st2))
    st = st1 + st2 
    val = []
    
    for i in range(1, len(st)):
        x = pre[st[i]] - pre[st[i-1]] - abs(h[st[i]] - h[st[i-1]])
        val.append(x)
    val.sort(reverse=True)
    ans = pre[n-1]
    for i in range(min(m, len(st)-1)):
        ans -= val[i]
    print(ans)

C++(clang++ 11.0.1) 解法, 执行用时: 73ms, 内存消耗: 5480K, 提交时间: 2023-06-09 20:48:11

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int ans,n,m,h[N],Max[N];
vector<int> v;

signed main()
{
	cin >>n >>m;
	for(int i=1;i<=n;i++)
	{
		cin >>h[i];
		if(i!=1) ans += abs(h[i]-h[i-1]);
	}
	
	for(int i=n;i>=1;i--)
		Max[i] = max(Max[i+1],h[i]);
	
	int l = 1,x = 0,y = 0;
	for(int i=2;i<=n;i++)
	{
		x += abs(h[i]-h[i-1]);
		if(h[i]>=h[l]) v.push_back(x-abs(h[i]-h[l])),x = 0,l = i,y = 0;
		else if(h[i]>y && Max[i+1]<=h[i]) v.push_back(x-abs(h[i]-h[l])),x = 0,l = i,y = 0;
		else y = max(y,h[i]);
	}
	
	sort(v.begin(),v.end(),greater<int>());
	
	for(int i=0;i<min(m,(int)v.size());i++)
		ans -= v[i];
	
	cout <<ans <<endl;
	
	return 0;
}

Python3 解法, 执行用时: 573ms, 内存消耗: 41396K, 提交时间: 2023-06-26 12:03:45

l=0
r=0
t=0
rs=0
ps={}
sc=[]
def rread(): 
    return int(input())
def fread(): 
    return [int(_x) for _x in input().split()]
n,m=fread()
ps[n]=0
ps[0]=0
sa=list(map(int,input().split()))
for i in range(1,n):
    ps[i]=ps[i-1]+abs(sa[i]-sa[i-1])
    if sa[i]>=sa[l]:
        rs=ps[i]-ps[l]-abs(sa[i]-sa[l])
        sc.append((rs))
        t+=1
        l=i
r=n-1
for i in range(n-2,l-1,-1):
    if sa[i]>=sa[r]:
        rs=ps[r]-ps[i]-abs(sa[r]-sa[i])
        sc.append((rs))
        t+=1
        r=i
sc.sort(reverse=True)
n-=1
l=min(t,m)
for i in range(0,l):
    r=sc[i]
    ps[n]-=r
print(ps[n])

详情