暑假提高组集训Day1 T1

时间:2021-01-10 09:48:49

说实话,今天的题真的有点难!

~备受打击~

我们先来看一看第一题吧

暑假提高组集训Day1 T1

暑假提高组集训Day1 T1

 

 看起来好像不太简单,其实并不难

下面来提供两种方法吧

1.做法一

//签到题 
/*

那么这一题就是告诉你n个点的坐标,把它们分别放到 0,0 0,1 0,2  ... 0,n-1
每一次可以把一个点向上下左右移动单位长度
那么我们可以先把他们到横轴的距离先累加起来
相当于都移动到了横轴上
我们可以贪心地想一下
已经到位的点肯定最好就不要动啦
然后把剩下的点的x坐标进行排序
然后插到空儿里
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int Leftx[1000005];
int vis[1000005];
int main()
{
//  freopen("checkin.in","r",stdin);
//  freopen("checkin.out","w",stdout);
    unsigned long long ans=0;
    scanf("%d",&n);
    int t=0,x,y;
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);//输入
        ans+=abs(y);//先把它们放到x轴上,就相当于加上 纵坐标y与横轴之间的距离
        if(!(x>=0&&x<n))
            Leftx[++t]=x;//如果不在0~n-1的范围内,就把它们存起来
        else
            vis[x]=1;//否则标记起来
    }
    sort(Leftx+1,Leftx+t+1);//把剩下的点按照x坐标进行排序
    int T=0;
    for(int i=0;i<n;i++){
        if(vis[i])
            continue;
        T++;//接下来就是挨个插到空儿里
        ans+=abs(i-Leftx[T]);//算法竞赛入门经典第二版
    }
    cout<<ans;
    return 0;

}

 2.做法二

 

其实就是把每一个点先进行排序,然后按顺序放进去,把每一个点要移动的距离累加起来

 

 

心得:提高组Day1T1 其实并不难

像这一道题就是一道贪心 模拟一下就能很轻松地解决~

 

p.s.下一道题就很坑了!!!