CF670B Game of Robots 题解

AzureMist · 2022-07-27 10:55:55 · 题解

这题较为简单，可以评红。

公式法(推荐)

核心在于套用公式：

找已经完成的行数：

while(i*(i+1)/2<k) i++;

以及计算这是新的一行的第几个：

cout<<a[k-i*(i-1)/2-1];

注意这里是 i\times(i-1)/2，因为循环结束后，i\times(i+1)/2 刚好大于 k，这时只要把 i 减掉 1 就能得到最大的满足 i\times(i+1)/2<k 的 i.

如果你也是这么写的，最后记得还要减掉 1，定义一个数组 a_n，它的下标只能是从 0 到 n-1 ，这个常识大家应该都知道。

AC Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n,k,i;
    cin>>n>>k;
    ll a[n];
    for(i=0;i<=n-1;i++) cin>>a[i];
    i=1;
    while(i*(i+1)/2<k) i++;
    cout<<a[k-i*(i-1)/2-1];
    return 0;
}

当然，你也可以用更正常的写法

就像这样：

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100005];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(i<k) k-=i;
        else
        {
            cout<<a[k];
            return 0;
        }
    }
    return 0;
}

这么写可以有效地帮助你避免公式里那些乱七八糟的东西。