奶牛排队的题解

有 N 头牛排成一列，有的面朝前，有的面朝后。
每次操作可以选择任意连续的 K 头牛，并改变它们的朝向。
请求出最小的 K，使得将所有牛的朝向都变为朝前所需的操作次数最少。

我们去枚举 $k$，然后贪心去check

复杂度 O ( n 3 ) O(n^3) O(n3)

#include 
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){T RR=1;FF=0;char CH=getchar();for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);FF*=RR;
}
template<typename T>inline void write(T x){if(x<0)putchar('-'),x*=-1;if(x>9)write(x/10);putchar(x%10+48);
}
template<typename T>inline void writen(T x){write(x);puts("");
}
int n,a[3010],ans=INT_MAX,xi,b[3010];
queue<int>q;
int work(int x){for(int i=1;i<=n;i++)b[i]=a[i];int s=0;for(int i=1;i<=n;i++){if(b[i]%2==1){if(i+x-1>n)return INT_MAX;for(int i=1;i<k;i++)b[i+k]^=1;s++;}}return s;
}
int main(){read(n);for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=n;i++){int x=work(i);if(x<ans){xi=i;ans=x;}}cout<<xi;return 0;
}

这样就有90分了。

100分做法有2种。都是去优化上述算法给后面数加的浪费时间的问题。

• 可以差分

#include 
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){T RR=1;FF=0;char CH=getchar();for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);FF*=RR;
}
template<typename T>inline void write(T x){if(x<0)putchar('-'),x*=-1;if(x>9)write(x/10);putchar(x%10+48);
}
template<typename T>inline void writen(T x){write(x);puts("");
}
int n,a[3010],ans=INT_MAX,xi,b[3010];
queue<int>q;
int work(int x){memset(b,0,sizeof(b));int s=0;for(int i=1;i<=n;i++){b[i]+=b[i-1];if((b[i]+a[i])%2==1){if(i+x-1>n)return INT_MAX;b[i]++;b[i+x]--;s++;}}return s;
}
int main(){read(n);for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=n;i++){int x=work(i);if(x<ans){xi=i;ans=x;}}cout<<xi;return 0;
}

• 可以用单调队列

#include 
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){T RR=1;FF=0;char CH=getchar();for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);FF*=RR;
}
template<typename T>inline void write(T x){if(x<0)putchar('-'),x*=-1;if(x>9)write(x/10);putchar(x%10+48);
}
template<typename T>inline void writen(T x){write(x);puts("");
}
int n,a[3010],ans=INT_MAX,xi,b[3010];
queue<int>q;
int work(int x){while(q.size())q.pop();int s=0;for(int i=1;i<=n;i++){while(q.size()&&i-q.front()>=x)q.pop();if((a[i]+q.size())%2==1){if(i+x-1>n)return INT_MAX;s++,q.push(i);}}return s;
}
int main(){read(n);for(int i=1;i<=n;i++)read(a[i]);for(int i=1;i<=n;i++){int x=work(i);if(x<ans){xi=i;ans=x;}}cout<<xi;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！