智慧软文网站,化工材料 技术支持 东莞网站建设,网址与网站的区别,门户网站如何制作题干#xff1a;
问题描述 数组A中共有n个元素#xff0c;初始全为0。你可以对数组进行两种操作#xff1a;1、将数组中的一个元素加1#xff1b;2、将数组中所有元素乘2。求将数组A从初始状态变为目标状态B所需要的最少操作数。
输入格式 第一行一个正整数n表示数组中元…题干
问题描述 数组A中共有n个元素初始全为0。你可以对数组进行两种操作1、将数组中的一个元素加12、将数组中所有元素乘2。求将数组A从初始状态变为目标状态B所需要的最少操作数。
输入格式 第一行一个正整数n表示数组中元素的个数 第二行n个正整数表示目标状态B中的元素
输出格式 输出一行表示最少操作数
样例输入
2 7 8
样例输出
7
数据规模和约定 n50B[i]1000 解题报告 一眼bfs再读题发现不能这样做乘2操作是全数组一起的然后倒着做一下就出来了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
int a[MAX],n;
bool ok() {for(int i 1; in; i) {if(a[i]!0) return 1;}return 0 ;
}
bool allou() {for(int i 1; in; i) {if(a[i]1) return 0 ;}return 1 ;
}
int main()
{cinn;int ans 0;for(int i 1; in; i) scanf(%d,ai);while(ok()) {if(allou()) {ans;for(int i 1; in; i) a[i]/2;continue;}for(int i 1; in; i) {if(a[i]1) ans,a[i]--;}}cout ans;return 0 ;}错误代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
int a[MAX],ans2[MAX];
struct Node {ll v;int step;int jia,ch; Node(){}Node(ll v,int step,int jia,int ch):v(v),step(step),jia(jia),ch(ch){}
};
Node bfs(ll a,ll b) {queueNode q;q.push(Node(a,0,0,0));while(q.size()) {Node cur q.front();q.pop();if(cur.v b) return cur;ll nowv cur.v1;if(nowv b*2) q.push(Node(nowv,cur.step1,cur.jia1,cur.ch));nowv cur.v*2;if(nowv b*2) q.push(Node(nowv,cur.step1,cur.jia,cur.ch1)); }return Node(0,0,0,0);
}
int main()
{int n;int ans10;cinn;for(int i 1; in; i) {scanf(%d,ai);Node res bfs(0,1ll*a[i]);ans1 res.jia;ans2[i] res.ch;}int tmp *min_element(ans21,ans2n1);for(int i 1; in; i) {ans1 (ans2[i] - tmp) * 2;}printf(%d\n,ans1tmp);return 0 ;}
