贪心可不是件简单事儿.
sort大法好==.
牺牲的任务只能在两个最大惩罚值中的最后一个任务的前面,只有牺牲前面的任务才能使最大惩罚值的值减小,注意这里是牺牲,就表示有可能牺牲这个任务后,该任务的惩罚值变成了最大惩罚值的其中一个。
方法2 二分套二分
优先队列维护
1 2 3//坐标缩小后就可以更方便的选择 double pos = (double)i / n * (n + m);//原来雕像的位置 ans += fabs(pos - floor(pos + 0.5))/(n + m);//*n+m后就选四舍五入最近的
围成一个圈每个人拿r[i]个礼物,相邻不相同
123456789101112131415161718 | bool check(int p){ int x = a[1], y = p - a[1];//bound left[1] = x,right[1] = 0; for (int i = 2; i <= n; i++) { if (i & 1) { right[i] = min(a[i],y - right[i-1]);//奇数尽量拿右边的 left[i] = a[i] - right[i]; } else { left[i] = min(a[i], x - left[i-1]);//偶数尽量拿左边的 right[i] = a[i] - left[i]; } } return left[n] == 0;} |
---|
Ai - Aj
尽量大
维护小于j的最大i值 MaxAi = max(Aj,MaxAi)
if (ans == maxn) ans = 0
尺取法 1 2 3 4 5 6 7 8 9for (ptr1 = ptr2 = 0; ptr2 < N; ptr2++) { sum += a[ptr2];//每次后面的指针后移 while (ptr1 <= ptr2 && sum - a[ptr1] >= S) { sum -= a[ptr1]; ptr1++; } if (sum >= S)update(ans, ptr2 - ptr1 + 1); } 1 2 3 4 5 6 7 8 9 10 11for (ptr1 = ptr2 = 0; ptr2 < N; ) { while (sum < S && ptr2 < N ) { sum += a[ptr2]; ptr2++; } while (sum >= S && ptr1 < ptr2) { update(ans, ptr2 - ptr1); sum -= a[ptr1]; ptr1++; } }
二分模板= =
1234567891011121314151617181920 | //整数while(l < r){ int m = l + (r - l + 1) / 2; if(check(m)) l = m; else r = m - 1;}l is answer //浮点数while (r - l > 0.000001) { double m = (r + l )/2; if (check(m)) { l = m; }else r = m;}//单调时最小位置i = lower_bound(a,a + n,val) - a; |
---|