iis7 网站用户权限,网站建设科技公司,android开发框架,衡水专业做网站付账问题#xff0c;关键是要了解整型的范围#xff0c;确定获取输入数据的变量类型 需要注意的是int的十进制范围-32768 ~ 32767#xff0c;那么我们可以知道#xff0c;人数n是可以用int来装的#xff0c;需付款数S应该是long long#xff0c;获取的每个人初始钱数也应…付账问题关键是要了解整型的范围确定获取输入数据的变量类型 需要注意的是int的十进制范围-32768 ~ 32767那么我们可以知道人数n是可以用int来装的需付款数S应该是long long获取的每个人初始钱数也应该是long long 同时由于最终结果才要求用小数在中间计算里尽量不要出现除法如果可以的话避免除法丢失精度
#includeiostream
#includebits/stdc.h
using namespace std;
static bool comp(const long long a,const long long b){return a b;
}
int main(){long long n;long long s;cinns;vectorlong long money;for(auto i 0;i n;i){long long a;cina;money.push_back(a);}sort(money.begin(),money.end(),comp);double avg 1.0 * s / n ;double sum 0.0;for(auto i 0;i n;i){if(money[i] * (n-i) s){sum (money[i] - avg) * (money[i] - avg); s - money[i];}else{double finalAvg 1.0 * s / (n-i) ;sum (finalAvg -avg)*(finalAvg -avg)* (n-i);break;}}printf(%.4lf,sqrt(sum / n));return 0;
}不过这道题很奇怪判题系统在我使用变量S的时候判错把变量S改为小写的s就正确了double avg 1.0 * s / n ;这种语句1.0在后面乘也是错的改个顺序又没事了没搞懂。。。 这道题一开始想着数据量小直接回溯法没想到这都能超时只能从回溯递归的暴力解改回动态规划了不过我这个不是很熟可以大概讲讲暴力-dp的修改思路
首先暴力回溯是有可能不断走前几轮已经走过的路径的如果强行算下去实际的时间复杂度O(n!)很大无法接受。这个时候使用dp其实就是把已经经历过的状态都记录下来当再次经历这个状态时就从dp的状态表里获取已有的数据这样相当于把计算量大大削减时间复杂度甚至可以到O(n)
想要把算法实现从暴力回溯改到dp实际上就是从自顶向下的递归改到自底向上的递推或是从自底向上的递归改到自顶向下的递推。我们首先要找出递归算法中原问题和子问题的自变量是啥也就是状态比如dfs里面的自变量就是横纵坐标i和j然后实际的结果是啥这个一般就是题目要你求的解也是你递归函数最后在返回时要得到的东西那么dp状态表我们就可以知道了有一个状态dp状态表就是一维的两个就是二维dp[i][j]表示i和j状态变化可以得到的某某结果
然后在dp状态表里填入base case这就是看是从自顶向下的递归改到自底向上的递推或是从自底向上的递归改到自顶向下的递推前者的base case就在后面因为要改成自底向上的递推后者就是在前面因为要改成自顶向下的递推
状态转移方程就看你的递归函数的实现其实就是递归的逆过程递归的各个状态咋倒回来
可以看看我这道题的解法一开始是用的dfs递归后续写了一个逆过程递推函数traceback体会一下
#includebits/stdc.h
#includeiostream
using namespace std;vectorvectorint matrix;
vectorvectorint dp;
vectorint nextVec;
int res INT_MIN;
void resInit(int n){for(int i 0;i n;i){vectorint vec(n,0);matrix.push_back(vec);dp.push_back(vec);}for(int i 1;i n;i){for(int j 0;j i;j){cinmatrix[i-1][j];if(i n){dp[i-1][j] matrix[i-1][j]; }}}for(int i 0;i 2;i){nextVec.push_back(i);}}
void traceback(int n){//base case 在dp初始化时已经做好 - 第n-1行for(int i n-2;i 0;i--){for(int j 0;j n;j){if(i1 n j1 n){dp[i][j] max(dp[i1][j] matrix[i][j],dp[i1][j1] matrix[i][j]);}else if(i1 n j1 n){dp[i][j] dp[i1][j] matrix[i][j];} }}}/*void dfs(vectorint chooseList,int sum,int i,int j,int n){if(i 0 || i n-1 ){res (res sum) ? sum : res;return; }for(int c : chooseList){dfs(chooseList,summatrix[i][j],i1,jc,n);}return;
}*/int main(){int n;cinn;resInit(n);//dfs(nextVec,0,0,0,n);// printf(%d,res);traceback(n);printf(%d,dp[0][0]);return 0;
}
