二次函数 + 三分算法

系统管理员 2022-09-09 09:14 123阅读 0赞

不用三分也可以，就是一个二次函数

#include<iostream>
    #include<vector>
    #include<algorithm>
    
    #define ll long long
    using namespace std;
    
    vector<ll> v[55];
    ll A, B, C, D, N;
    
    
    ll g(ll x)
    { 
    	ll res = 0;
    	while(x)
    	{ 
    		res += x % 10;
    		x /= 10;
    	}
    	return res;
    }
    
    void init()
    { 
    	for(ll i = 1; i <= 1e6; i++) v[g(i)].push_back(i);
    }
    
    
    ll cal(ll g, ll x)
    { 
    	return A*x*x*g + B*x*x + C*x*g*g + D*x*g; 
    }
    
    ll sanf(ll pos, ll r)
    { 
    	ll l = 0;
    	while(r - l > 3)
    	{ 
    		ll lm = l + (r - l) / 3;
    		ll rm = r - (r - l) / 3;
    		ll L = cal(pos, v[pos][lm]);
    		ll R = cal(pos, v[pos][rm]);
    		if(R >= L) r = rm;
    		else l = lm;
    	}
    	ll res = 1e18;
    	for(ll i = l; i <= r; i++) res = min(res, cal(pos,v[pos][i]));
    	return res;
    }
    
    int main()
    { 
    	init();
    	int t;
    	cin >> t;
    	while(t--){ 
    		scanf("%lld %lld %lld %lld %lld", &A,&B,&C,&D,&N);
    		ll res = 9e18;
    		for(ll i = 1; i <= 54; i++)
    		{ 
    			if(v[i].size() == 0 or v[i][0] > N) continue;
    			int pos = upper_bound(v[i].begin(),v[i].end(),N)-v[i].begin()-1;
    			if(pos < 0) continue;
    			if(A*i + B > 0) res = min(res, sanf(i, pos)); // 开口向上
    			else res = min(res ,min(cal(i, v[i][0]), cal(i,v[i][pos])));
    		}
    		printf("%lld\n", res);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关 Element 分页二次封装

对分页进行了二次封装 ![效果图][2020033110303538.png] 调用 <div class="pagination-container">

骑猪看日落/ 2023年07月19日 12:29/ 0 赞/ 24 阅读

相关三分查找算法

原理三分法的原理也很简单，和二分法几乎一模一样，只不过我们分隔区间的时候，不是将区间一分为二，而是一分为三。之后，我们同样通过缩小区间的方法来确定要查找的值所在。但

爱被打了一巴掌/ 2023年02月20日 04:56/ 0 赞/ 23 阅读

相关算法题目——二次函数三分求极值(HDU-3714）

题目链接：[HDU-3714][] 题目描述：对于N个二次函数，求每个二次函数的最小值中的最大值思路：使用三分法求极值（递归调用）对于这种在指定区间里

桃扇骨/ 2022年09月14日 02:22/ 0 赞/ 151 阅读

相关二次函数 + 三分算法

不用三分也可以，就是一个二次函数 include<iostream> include<vector> include<algorithm>

系统管理员/ 2022年09月09日 09:14/ 0 赞/ 124 阅读

相关二次封装函数

题目描述已知函数 fn 执行需要 3 个参数。请实现函数 partial，调用之后满足如下条件： 1、返回一个函数 result，该函数接受一个参数 2、执行

小鱼儿/ 2022年06月04日 05:56/ 0 赞/ 280 阅读

相关 ElementUI 分页组件二次封装

更新记录：修复了删除当前所有数据未触发退回上一页问题。改善了调用方式，仅需传入分页对象与绑定查询事件。改为通过 model 更新分页对象。修复

Myth丶恋晨/ 2022年05月08日 23:58/ 0 赞/ 538 阅读

相关算法之二分查找

概念二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到想要查找的元素，或是区间被缩小

柔光的暖阳◎/ 2022年04月17日 03:58/ 0 赞/ 226 阅读

相关（三）使用TensorFlow对一元二次函数进行预测

1、导入所需的库 import tensorflow as tf import numpy as np import matplotlib.pyp

我会带着你远行/ 2022年03月01日 11:42/ 0 赞/ 210 阅读

相关【算法•日更•第二期】查找算法：三分VS二分

▎前言：函数　　如果你已经上过初二的数学课了，那么你十有八九会被函数折磨到吐血，这是一种中考压轴题类的题目，往往分类讨论到你恶心。不过没学过也不打紧，现场讲解一下： ☞『

缺乏、安全感/ 2021年11月22日 08:02/ 0 赞/ 300 阅读

相关智商恢复训练(二分，三分)

整数二分 1.mid在左边， \[ l , m i d \] 与 \[ m i d + 1 , r \] \[l,mid\] 与\[mid+1,r\] \[l,mid\]与

╰半夏微凉°/ 2021年09月17日 23:42/ 0 赞/ 324 阅读