作者:arashilan | 来源:互联网 | 2023-05-17 19:36
题意给2n个实数。拿n个出来做floor,剩下的取ceil。d为操作前后元素的和之差的绝对值,求最小的d。思路PS:感觉像这样的现将所有的元素统一操作一遍,然后从中间选若
题意
给2n个实数。
拿n个出来做floor,剩下的取ceil。
d为操作前后元素的和之差的绝对值,求最小的d。
思路
PS:感觉像这样的
现将所有的元素统一操作一遍,然后从中间选若干个
遇到的题有贪心,dp,枚举。。
快形成一种思路了,应该总结下类似的题。。
设小数部分x[i]
先将所有的数取floor,d =
−∑x[i]
然后只要选n个数出来ceil
将floor换成ceil就是加上1 (ceil(a[i]) = floor(a[i])+x+1-x)
但是x = 0.0的数,ceil和floor的结果都是自己
设满足 x = 0.0 的数的个数为m
1)m >= n
枚举区间 [d, d+2n-m]
2)m 枚举区间 [d+n-m, d+n]
#include
using namespace std;
#define SPEED_UP iostream::sync_with_stdio(false);
#define FIXED_FLOAT cout.setf(ios::fixed, ios::floatfield);
#define rep(i, s, t) for(int (i)=(s);(i)<=(t);++(i))
#define urep(i, s, t) for(int (i)=(s);(i)>=(t);--(i))
#define in_bound(l, r, i) (l)<=(i)&&(i)<(r)
#define pb push_back
typedef long long LL;
const int inf = INT_MAX/2;
const int Maxn = 4005;
const LL Mod = 1000000007;
string s;
LL k, p;
LL opt_pow_n(LL x, unsigned int n)
{
LL pw = 1;
while(n > 0){
if (n&1)
pw = pw*x%Mod;
x = x*x%Mod;
n = n >> 1;
}
return pw;
}
LL go(LL n) {
if (n == 1) return 1;
LL tmp = go(n/2);
if (n&1) {
return ((tmp+opt_pow_n(p, n/2)*tmp%Mod)%Mod+opt_pow_n(p, n-1))%Mod;
}
else {
return (tmp+opt_pow_n(p, n/2)*tmp%Mod)%Mod;
}
}
LL solve() {
LL ans = 0, n = s.length();
p = opt_pow_n(2, n);
LL base = go(k);
0;
}