首页 > 代码库 > bjfu1099 度度熊大战僵尸
bjfu1099 度度熊大战僵尸
这也是2011年百度之星的一道题。
这题我就是乱搞搞过的，打代码之前自己心里也没底，不知道能不能过的。
我的做法很简单，就是按时间顺序依次构造能杀死的僵尸血量，找到第k小的。构造的方法也很暴力：对t时刻，第i个武器新构造出来的血量，就是用ai+t*bi依次去加之前时刻构造出来的血量。所以解题的关键就在于不断地对这个方法进行剪枝与优化。
第一个优化是，t只用从1到k，而不用再往后，很好理解。
第二，考虑如何存储已经产生的血量。我是用了一个set保存所有的血量，然后每一次循环时把set中的内容导出到一个数组里。往set里插入数据和查找数据都是log n的，所以把数据导出到数组里复杂度为n*log(n)。这里又可以加入一个优化，每次导出到数组里的元素只用前K个。
第三个优化，如果当t时刻，所有的ai+bi*t都比当前的结果大，则可以结束。
这样打完之后，自己测了几组数据，很快出结果，但是交上去依然超时。于是自己构造了几组变态数据，一测，发现瓶颈依然在set那里，因为对于大型的测试数据，后来的时刻产生的大量血量值都是以前出现过的，如果用hash来判断血量值是否出现过，就能把这里的复杂度从log(n)降到O(1)，因为这里是瓶颈，所以效果很明显。果然，加上以后就过了。
代码如下：
/* * bjfu1099 * Author : ben */#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>#include <stack>#include <string>#include <vector>#include <deque>#include <list>#include <functional>#include <numeric>#include <cctype>using namespace std;#ifdef ON_LOCAL_DEBUG#else#endiftypedef long long LL;const int maxn = 11;int N, K;int a[maxn], b[maxn];int buf[51000];set<int> S;const int maxh = 1000007;bool hash[maxh];int hval[maxh];void hash_insert(int num) { int k = num % maxh; while (hash[k] && hval[k] != num) { k = (k + 1) % maxh; } if (!hash[k]) { hash[k] = true; hval[k] = num; }}bool hash_find(int num) { int k = num % maxh; while (hash[k] && hval[k] != num) { k = (k + 1) % maxh; } return hash[k];}int work() { bool hasnew = true; S.insert(0); hash_insert(0); int offset, I; for (int t = 1; t <= K; t++) { if (hasnew) { I = 0; set<int>::iterator it = S.begin(); while (it != S.end() && I <= K) { buf[I++] = *(it++); } hasnew = false; } offset = (I > K) ? buf[K] : 0x7fffffff;// printf("t = %d, offset = %d, I = %d\n", t, offset, I); bool flag = false; for (int i = 0; i < N; i++) { a[i] += b[i]; if (a[i] > offset) { continue; } for (int j = 0; j < I; j++) { int p = a[i] + buf[j]; if (p < offset) { flag = true; if (!hash_find(p)) {//对于大型的测试数据，后面的插入太多重复，用hash能降掉这里的logn的复杂度// if (S.count(p) <= 0) { hasnew = true; S.insert(p); hash_insert(p); } } else { break;; } } } if (!flag) { break; } } return buf[K];}int main() {#ifdef ON_LOCAL_DEBUG freopen("data.in", "r", stdin);#endif memset(hash, false, sizeof(hash)); scanf("%d%d", &N, &K); for (int i = 0; i < N; i++) { scanf("%d%d", &a[i], &b[i]); } printf("%d\n", work()); return 0;}
bjfu1099 度度熊大战僵尸
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。