题意
定义g(x)为x的各数位之和
求该方程:
在给定x范围内的最小值
思路:
一个x对应一个g(x)，一个g(x)对应多个x
由于g(x)最多取到54,所以可以枚举所有的g(x)所以想到当取到g(x)的时候,只取能使原方程f(x)最小的那几个x
当枚举g(x)的时候,g(x)看作一个常数,此时方程就变成了一个二元一次方程(A*g(x)+B==0的时候为一元一次方程)
那么此时的x可以当做定义域,使得函数最小的x,无论是不同开口朝向的二元一次方程还是一元一次方程,最小值一定在
1.左右端点
2.对称轴左右两边(对称轴不一定是整数)
中取到
代码
#include<iostream>
#include<map>
#include<cmath>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#define pb push_back
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(),(x).end()
#define _for(i, a) for(int i = 0; i < (a); ++i)
#define _rep(i, a, b) for(int i = (a);i <= (b); ++i)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
typedef pair<int,int> PII;const int INF=4e18;
const int MOD=1e9+7;
const int N=1e6,M=2*N;
vector<int> v[100];
int a,b,c,d,n=1000000,ta,tb,x;
int get(int x){int res=0;while(x){res+=x%10;x/=10;}return res;
}
void init(){_rep(i,1,N){int t=get(i);v[t].pb(i);}
}
int right(int g,int x){auto t=lower_bound(v[g].begin(),v[g].end(),x);if(t==v[g].end()) return -1;return *t;
}
int left(int g,int x){auto t=lower_bound(v[g].begin(),v[g].end(),x);if(t==v[g].begin()) return -1;t--;return *t;
}
bool check(int x){return x>=1&&x<=n;
}
int cal(){return x*x*ta+tb*x;
}
void solve(){cin>>a>>b>>c>>d>>n;int res=INF;_rep(i,1,54){ta=a*i+b;tb=c*i*i+d*i;double mid=0;if(ta!=0) mid=(tb/(-2*ta));int midl=floor(mid);int midr=ceil(mid);//对称轴左边x=left(i,midl);if(check(x)) res=min(res,cal());x=right(i,midl);if(check(x)) res=min(res,cal());//对称轴右边x=left(i,midr);if(check(x)) res=min(res,cal());x=right(i,midr);if(check(x)) res=min(res,cal());//左端点x=right(i,1);if(check(x)) res=min(res,cal());//右端点x=left(i,n);if(check(x)) res=min(res,cal());x=right(i,n);if(check(x)) res=min(res,cal());}cout<<res<<endl;//
}
signed main(){init();IOS;int T=1;cin>>T;_rep(i,1,T){solve();}return 0;
}实现
