首页 > 代码库 > CodeForces 352C-- Jeff and Rounding
CodeForces 352C-- Jeff and Rounding
http://codeforces.com/problemset/problem/352/C
首先要明白一点:
给n*2个数,找到n个这样的数对,(ai,aj) ,前一个数向下取整,后一个数向下取整,输出修改后的序列和 与 原序列和 的差的最小的绝对值
首先要明白一点:
设res是 所有数都向上取整时的序列和 与 原序列和 的差值,如果一个数 ai 要改变为向下取整的话(ai 不是整数),res=fabs(res-1) ;
由于以上的推导有一个条件:ai不为整数
所以我们需要统计一下序列中整数的个数num,然后枚举减1 的次数,从而发现最优结果
由于需要向上向上取整与向下去整的个数都等于n,
所以枚举的范围是[max(0,n-num),min(n,2*n-num)]
代码:
#include<bits/stdc++.h> using namespace std; const double eps = 1e-6; const int MAXN = 8000; double a[MAXN]; int main() { //freopen("data.in","r",stdin); int n; cin >> n; double x; for (int i = 0; i < 2 * n; i++) { cin >> a[i]; } double sum = 0; int num = 0; for (int i = 0; i < 2 * n; i++) { x = ((int)a[i] + 1) * 1.0 - a[i]; if (fabs(x - 1) <= eps) { num++; } else { sum += x; } } //cout<<num<<endl; //cout<<sum<<endl; int m = 0; if (num < n) { m = n - num; } double res = 0x3f3f3f3f * 1.0; for (; m <= min(2 * n - num, n); m++) { res = min(res, fabs(sum - m)); } //printf("%.3llf\n",res); cout << fixed << setprecision(3) << res << endl; }
CodeForces 352C-- Jeff and Rounding
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。