题解：UVA12918 Lucky Thief

Gilbert1206 · 2024-11-06 19:47:36 · 题解

题意：

题目描述

一个非常幸运的小偷
在一条有 m 栋房屋的街道上找到 n 个钥匙。他知道每把钥匙都只打开一个门，所以他想知道哪扇门的钥匙对应哪扇门，但他也想减少尝试次数，以免使安全系统失效。

输入

第一行包含一个整数 T （T≤100000），表示测试用例的数量。这 以下 T 行包含两个整数 n 和 m，1≤n≤m≤100000

输出

打印窃贼必须执行的最小尝试次数，以便知道哪把钥匙打开了哪扇门。

思路：

自写样例找规律

.in

1
3 6

.out

12

过程

• 第一次找至多5次

• 第二次因为已经找到了1个钥匙对应的门，剩下就是5-1=4个

• 第三次因为已经找到了2个钥匙对应的门剩下就为4-1=3个

• 最后相加 5+4+3=12

  规律

• 5+4+3为递减

• 注意 m=first-1,n=last (first指第一次找的次数，last指最后一次要找的次数)

• 所以发现这是一个等差数列，公式为：

  ans=\frac{(last+first)\times len}{2}

• 代入m,n

  ans = \frac{(m - 1) + (m - n) \times n }{ 2}

• 化简

  ans=\frac{(2*m-n-1)*n}{2}

AC code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, m;
        cin >> n >> m;
        long long ans = ((2*m-n-1)*n)/2;//十年OI一场空，不开long long见祖宗
        cout << ans << endl;
    }
    return 0;
}