列表

详情

NC200114. Little Gyro and Numbers

描述

Little Gyro has just found a number sequence a_1,a_2,...,a_n which length is n in his right pocket, while his left pocket is totally empty. As Little Gyro is bored, he decides to play with these numbers.
Then, Little Gyro is prepared to play with the number sequence with n operations by doing the following steps:
1. In the i-th turn, Little Gyro will take out a number a_i from his right pocket with its initial permutation, as well as put it into his left pocket.
2. Then, Little Gyro let number .
3. After that, Little Gyro take out a number a_j from all the remained numbers in his right pocket one by one, set down the number and let number , and then put the number a_j back to his right pocket immediately.
4. Finally, for each number pair

, Little Gyro will calculate and , and count how many pairs of numbers satisfied . After counting all the number pairs of the i-th turn, Little Gyro put the number a_i back to his right pocket with its initial position.
Now given an integer sequence, after these operations, Little Gyro wants to know the number of all the satisfied number pairs of each turn and ask you for help, please help him to count.

输入描述

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (2 ≤ n ≤ ), indicating the length of the sequence.
The second line contains n integers a_1,a_2,...,a_n (1 ≤ a_i ≤ ), indicating the given sequence.
It's guaranteed that the sum of n of all test cases will not exceed .

输出描述

For each test case, you should firstly print "Case X:" in the first line, indicating the case number.
And then output n lines, the i-th line contains an integer indicating the number of all the satisfied number pairs of number a_i in the i-th turn.

示例1

输入: 

2
3
1 2 5
4
4 5 6 7

输出: 

Case 1:
0
2
1
Case 2:
3
2
1
0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 404ms, 内存消耗: 6904K, 提交时间: 2020-05-30 22:58:56 

//#include <cstdio>
//#include <iostream>
//#include <algorithm>
#include<bits/stdc++.h>

using namespace std;

void read(int &x)
{
    x=0;
    char t;
    t=getchar();
    while(t<'0'||t>'9') t=getchar();
    while(t>='0'&&t<'10') 
    {
        x=x*10+t-'0';
        t=getchar();
    }
}
void write(int x)
{
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int a[100001],b[100001],t,p=0,c;
int main()
{
    read(t);
    p=0;
    while(t--)
    {
        p++;
        read(c);
        for(int i=0;i<c;i++)
    {
        read(a[i]);
        if(a[i]==2)
        {
            a[i]=4;
        }
        if(a[i]==1)
        {
            a[i]=1000000001;
        }
        b[i]=a[i];
    }
    sort(b,b+c);
        printf("Case %d:\n",p);
        int sum;
        for(int j=0;j<c;j++)
        {
            sum=c-(upper_bound(b,b+c,a[j])-b);
            write(sum);
            puts("");
        }
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 740ms, 内存消耗: 16864K, 提交时间: 2019-12-09 10:08:02 

#include<bits/stdc++.h>
#define ll long long

using namespace std;
double b[100005], a[100005];
int main()
{
    int n, t;
    scanf("%d",&t);
    for(int o=1;o<=t;o++)
    {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lf",&a[i]);
        b[i]=(1.0*log10(a[i]))/a[i];
        a[i]=b[i];
    }
    sort(b,b+n);
    printf("Case %d:\n",o);
    for(int i=0;i<n;i++)
    {
        printf("%d\n",lower_bound(b,b+n,a[i])-b);
    }
    }
    return 0;
}

上一题

© 2024 nowcoder.com