这是博客的自动同步,我让它自动同步到所有社交网络。有朋友跟我讲人人都快被我刷屏了,真是对不住。其实人人有屏蔽功能,不过我建议取消好友\关注。另外我根本不用人人这种SNS,请不要给我留言,我的强迫症让我保留了人人账号,打扰了。
晾衣服:n件衣服各含a_i水分,自然干一分钟一单位,放烘干机一分钟k单位,一次只能晒一件。求最短时间。
取C(mid) := 能在mid分钟内处理完,然后二分即可。
这里有两个很好玩的陷阱
①每分钟烘干k单位的水,于是我就想当然地除k向上取整了((a_i – mid) / k)。其实应该除以k-1,列个详细的算式:
设需要用x分钟的机器,那么自然风干需要mid – x分钟,x和mid需要满足:
k*x + (mid – x) >= a_i,即 x >= (a_i – mid) / (k – 1)。
②当k=1的时候,很显然会发生除零错误,需要特殊处理。
所以应该这么干:
#ifndef ONLINE_JUDGE #pragma warning(disable : 4996) #endif #include <iostream> #include <algorithm> using namespace std; #define MAX_A 100000 + 16 int n, a[MAX_A], k; bool C(int mid) { unsigned long long minutes(0); for (int i = 0; i < n; ++i) { int more = a[i] - mid; if (more > 0) { minutes += (more + k - 1) / k; // ceil if (minutes > mid) { return false; } } } return true; } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif std::ios::sync_with_stdio(false); std::cin.tie(0); cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i]; } cin >> k; --k; // x >= (a_i - mid) / (k - 1) if (k == 0) { cout << *max_element(a, a + n) << endl; } else { int lb = *min_element(a, a + n) / k, ub = *max_element(a, a + n); while (ub - lb > 1) { int mid = (lb + ub) >> 1; if (C(mid)) { ub = mid; } else { lb = mid; } } cout << ub << endl; } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
请问,判断二分结束的条件是如何确定的呢?什么时候是lb1?
其实都可以,如果是用ub-lb>1来判断,循环里面就可以写成ub=mid,lb=mid,
如果是ub>lb的话,循环里面可以写成ub=mid,lb=mid+1,另外,附个人博客地址http://www.cnblogs.com/akrusher/
666[嘻嘻]