首页 > 代码库 > topcoder srm 683 div1 -3
topcoder srm 683 div1 -3
1、有$n$堆石子，组成一个环形。初始时第$i$堆石子有$a_{i}$.现在每次操作可以将一个石子从某一堆移动到相邻的堆上。问最少多少次操作可以使得最后第 $i$堆有$b_{i}$个石子？$1\leq n \leq 1000$
思路：肯定存在相邻两堆满足不会存在任何操作在这两堆之间进行。然后就成为一条链，那么只需要维护链的前缀和即可判断当前堆和前一堆之间需要多少次操作。
#include <stdio.h>#include <string.h>#include <string>#include <iostream>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <stack>using namespace std;class MoveStones{public: long long get(vector<int> a,vector<int> b) { long long sum=0; int n=(int)a.size(); for(int i=0;i<n;++i) sum+=a[i]-b[i]; if(sum) return -1; if(n==1) return 0; long long ans=1e16; for(int i=0;i<n;++i) { long long pre=0; long long tmp=0; for(int j=1;j<=n;++j) { long long t=a[(i+j)%n]-b[(i+j)%n]; tmp+=abs(pre); pre+=t; } ans=min(ans,tmp); } return ans; }};
topcoder srm 683 div1 -3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。