序
今天是个好日子，开局多校D看起来就是个简单的二分模拟,马上动手写起来啊！然后一直写到了比赛结束(当然中途看了一下其他题,并且给队友提供了j题的解题思路)
反二分的2019牛客多校6D题
题目链接
哒哒马蹄终究是错
因为这个题目终极不是正规的二分做法！因为答案根本不满足二分算法中的答案单调性，比如如下反例
1
2
|
15 5
39 39 39 39 39 60 60 60 60 60 100 100 100 100 100
|
答案是199，而200不能是答案，201也不能是答案
(二分输出答案是216)(因为二分总是在较大数值的时候是满足的可能性极大的,所以二分后整体的结果偏大,其实有更小的答案漏掉了)
不过这题的美丽错误美就美在了它让人有种是二分的错误–(哒哒的马蹄，是个美丽的错误)
如何AC
不过因为数据比较弱(其实造一个完美避开二分的数据几乎是不可能在题目数据范围实现的，如果可以，那我把二分后往小的方向开得更远一下枚举，根据上面分析为了避免小概率事件还可以多搞一下向大的方向也枚举)，所以我们现在可以有两种做法
- 先二分，然后在这个ans下继续向小的方向枚举20项
- 因为答案的下界和上界相差很小，可以直接枚举
二分再向小方向走
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
/*
因为数据弱，所以不满足单调性的时候这样这样来凑一手
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int inf = 0x3f3f3f3f;
const int M = 1e3+10;
int T,n,K,v[M],sum,vis[M];
bool check(int x){
if(x*K<sum || x<v[n-1]) return false;
if(x>=v[n-1] && K>=n) return true;
for(int i=0;i<n;i++) vis[i]=0;
int tmp=0,ts=sum;
int i=1;
while(ts>0){
int tps = 0;
while(i<=n && vis[n-i]) i++;
if(n-i>=0) {
tps += v[n-i];
// cout<<"I get you! : "<<v[n-i]<<endl;
vis[n-i]=1;
}
else break;
while(tps<x){
int tn = upper_bound(v,v+n-i,x-tps)-v;
int j=1;
while(j<=tn && vis[tn-j]) j++;
if(tn-j>=0) {
tps += v[tn-j];
// cout<<"I get you! : "<<v[tn-j]<<endl;
vis[tn-j]=1;
}
else break;
}
// cout<<"How much is the tps "<<tps<<endl;
ts -= tps;
tmp++;
}
if(tmp>K) return false;
return true;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>T;int kase=1;
while(T--){
cin>>n>>K;
sum = 0;
for(int i=0;i<n;i++){
cin>>v[i]; sum+=v[i];
}
sort(v,v+n);
int l=1,r=1e6;
while(l<r) {
// cout<<"l: "<<l<<" r: "<<r<<endl;
int mid = (l+r)>>1;
if(check(mid)) r=mid;else l = mid+1;
}
int ans = l;
for(int i=ans;i>=ans-20;i--) if(check(i)) ans = i;
cout<<"Case #"<<kase++<<": "<<ans<<endl;
}
return 0;
}
|
正规做法-从下界开始枚举
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
// 代码来源--杭电的一个二人小分队 jesus
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1086;
int v[N],vis[N];
int n,k;
bool check(int vv){
int num=k;
for(int i=0;i<=n;i++){
vis[i]=0;
}
int left=n;
int maxx=n,no=1;
while(num){
int sp=vv;
for(int i=maxx;i>0;i--){
//如果当前剩余容量比最小的更小，不能继续装，退出循环
if(sp<v[no])break;
//如果当前剩余容量足够，并且物品i还没有装过，则装入
if(sp>=v[i]&&!vis[i]){
sp=sp-v[i];vis[i]=1;left--;
//如果无剩余，直接退出循环
if(!sp)break;
}
}
//压缩下次寻找的范围
while(vis[maxx])maxx--;
while(vis[no])no++;
num--;
}
//如果无剩余，则正好输出
if(!left)return 1;
return 0;
}
int main(){
int cases;
scanf("%d",&cases);
for(int ti=1;ti<=cases;ti++){
scanf("%d%d",&n,&k);
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&v[i]);
sum+=v[i];
}
sort(v+1,v+n+1);
int b=sum/k;
if(sum%k)b++;
int maxx=max(v[n],b);
int ans=maxx;
int i=maxx;
while(i){
if(check(i)){
ans=i;break;
}
i++;
}
printf("Case #%d: %d\n",ti,ans);
}
return 0;
}
|
每天一句叨叨
人生本来就是一场修行，人的基因把我们当做机器人，然后让我们为他们传递生命，所以给我们制造了很多激素，其中一些情绪激素让我们时而快乐时而悲伤，时而兴奋时而自闭，我们可能无法改变太多，唯有做的就是享受这个当机器人还能发发牢骚的快乐，并享受这一次人生的偶然，尽自己的快乐，去奋斗，去创造，因为平庸更使自己感到乏味…那就成为一个，不断进化，并快乐地享受其中的机器人吧
