AtCoder Regular Contest 086 D Non-decreasing

题目链接https://arc086.contest.atcoder.jp/tasks/arc086_b

题意:给你一个序列,有正有负,然后一个操作x\ y,表示把a_x值加到a_y上,现在用[0,2\*n]范围内个的操作把整个序列变成不严格单调递增的序列。

思路:考虑一个序列,如果全是正的,很显然我们可以用n个操作构造出这样一个序列:a_1,a_1+a_2,a_1+a_2+a_3,...,同理如果全是负的我们可以构造出这样一个序列a_1+a_2+...+a_n,a_1+a_2+...+a_n-1,...,但很明显这个序列有正有负,没有办法这样进行操作。所以我们找出序列的最大值和最小值,比较它们的绝对值,如果最大值的绝对值大于最小值的绝对值,我们就把这个最大值加到所有的数上使其变成一个全是正的序列,反之我们把这个最小值加到所有数上使其变成一个全是负的序列,这样我们再进行第一步的操作就可以构造出这样一个序列且操作数是2\*n-1个不会超过2\*n个。

int n;
int main(){
    read(n);
    int mn=1e6+5,mx=-1e6-5,pos1,pos2;
    for (int i=1;i<=n;i++){
        int x;read(x);
        if (mn>x){
            mn=x;
            pos1=i;
        }
        if (mx<x){
            mx=x;
            pos2=i;
        }
    }
    printf("%d\n",2*n-1);
    if (abs(mn)<abs(mx)){
        for (int i=1;i<=n;i++){
            printf("%d %d\n",pos2,i);
        }
        for (int i=2;i<=n;i++){
            printf("%d %d\n",i-1,i);
        }
    }
    else{
        for (int i=1;i<=n;i++){
            printf("%d %d\n",pos1,i);
        }
        for (int i=n;i>=2;i--){
            printf("%d %d\n",i,i-1);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注