前言
好多题不能再让我有进步了,我记录的也少了,还是说尽可能的记录我感想多的题目
今日学习记录
1. P14826 踩踩标 - 洛谷
关键词：数学
问题分析：
根据计算 y 的最小值,给定 n 和 k,其中.
核心思路: 这里很重要,要讲一个思维性的突破 我们在做这种数学的时候,比如蓝桥杯那样的数学填空题时,并不是真的让你算完了再填答案,而是真正的使用计算机去算,但是怎么使用计算机就是主要问题,这里详细说明 先点明主题,使用计算机就是使用他的强大的计算能力,我们学算法的都知道,我们先使用暴力模拟,再想办法设计合适的算法进行优化,所以回归本质就是枚举暴力,那么这里就是这样的 那么在实际思考数学题目的时候,我们该怎么想,比如当前这道题目 我们可以看到,有三个变量,两个式子,那么可以化简一个式子,使其中一个变量用其他变量表达 于是,只剩下两个变量了,那么我们开始使用枚举思想,都要枚举了,自然就假设我们已经知道枚举的那个数字,这样就直接思考后面的式子是否能成立,假设知道 x,y 能不能算出来 当然,我们不能无脑的去枚举(计算机的优势就在这里,因为我们要使用的是数学计算,时间复杂度在 O(n)左右,所以程序几乎可以跑 1~1e9 的数据,可以枚举的范围算是大的),我们要通过式子和题目的背景对变量进行范围约束,看这个变量的范围能否找到,优先考虑枚举范围明确的变量,这样要简单多,性能要好很多 这题我们可以看出,c>=0,所以,这里有个极值问题,当 a=b 的时候有最大值,所以可以取 a=b,得到,a 又大于 0,所以 a 的范围明确了, 这样所以的未知数都知道了,直接记录 y 的最小值就行了
**最终代码：
#include <bits/stdc++.h>
using namespace std;
#define ve vector
using ll = long long;
using ull = unsigned long long;
using sr = string;
using db = double;
using dll = double long;
const int MOD=998244353;
const ll INF=1e18;
const int DIR[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
int T;
void solve(){
ll n, k;
cin>>n>>k;
if(k == 0){
cout<<0<<endl;
return;
}
ll ans = k * n;
ll sqrt_n = sqrt(n);
for(ll a = 1;a <= sqrt_n;a++) {
ll b = n / a;
ll c = n - a * b;
ll val = a + b + k * c;
if(val < ans){
ans = val;
}
}
cout<<ans<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>T;
while(T--) solve();
}学到的点：
- 如何看待计算机中的数学题