文章

5

粉丝

9

获赞

2

访问

2.5k

头像
Minimum_Sum 题解:
推荐阅读
P1910 华东师范大学2022年机试
发布于2024年9月6日 00:27
阅读数 898

一个结论:最小化曼哈顿距离,根据这个结论暴力求解即可(可以满分但不是最优解,本渣渣不会线段树)

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int arr[n+10];
    int b[n+10];
    vector<int>v;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        b[i]=arr[i];
    }
    //sort(0)
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        for(int i=l;i<=r;i++){
            v.push_back(arr[i]);
        }
        int len=v.size();
        int x=0;
        if(len%2!=0){
            x=(arr[len])/2+1;
        }
        else{
            x=(arr[len])/2;
        }
        int sum=0;
        for(int i=l;i<=r;i++){
            sum+=abs(x-arr[i]);
        }
        cout<<sum<<endl;
    }


    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发