每日一题洛谷普及/提高-P1154奶牛分厩c++

无注释版

#include<iostream> #include<cstring> #include<cstdlib> using namespace std; bool ju(int n, int s[], int len, bool a[]) { memset(a, 0, n * sizeof(bool)); for (int j = 0; j < len; j++) { if (a[s[j] % n]) { return false; } a[s[j] % n] = true; } return true; } int main() { int n; cin >> n; int* s = new int[n]; for (int i = 0; i < n; i++) cin >> s[i]; bool* d = new bool[1000001](); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { d[abs(s[i] - s[j])] = true; } } bool* a = new bool[1000001]; for (int k = n;; k++) { bool flag = true; for (int t = k; t <= 1000000; t += k) { if (d[t]) { flag = false; break; } } if (flag&&ju(k, s, n,a)) { cout << k << endl; break; } } delete[] s; delete[] d; delete[] a; return 0; }

注释版

//本段代码优化了很多处，才正好卡在极限时间AC了。。。 //思路是通过一个个枚举K值来找出合适的最小K #include<iostream> #include<cstring> #include<cstdlib>//abs函数用来计算绝对值 using namespace std; //判断余数是否相同 bool ju(int n, int s[], int len, bool a[]) { memset(a, 0, n * sizeof(bool)); for (int j = 0; j < len; j++) { //如果已经有相同的余数，则K不符合条件，返回false if (a[s[j] % n]) { return false; } a[s[j] % n] = true; } //如果没有余数相同则符合条件，返回true return true; } int main() { int n; cin >> n; //优化1：动态内存分配 int* s = new int[n];//意思是开了一个s的数组，存上n个数据 for (int i = 0; i < n; i++) cin >> s[i]; //优化2：差值标记，如果一个差值d是K的倍数则一定不满足条件，因为余数相同 //bool类型的动态内存分配，每个数据要么是true要么是false，（）的意思是1000001个数据全部初始化为false bool* d = new bool[1000001](); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { d[abs(s[i] - s[j])] = true; } } //优化5：将a定义在主函数中，避免在ju函数中多次定义和释放 //a的作用是存储数据，没有余数时存储false，有一个余数时存储true，又有一个相同的余数时存储false bool* a = new bool[1000001]; //找出最小K //优化3：从n开始找 for (int k = n;; k++) { bool flag = true; for (int t = k; t <= 1000000; t += k) { //如果差值是K的倍数则不符 if (d[t]) { flag = false; break; } } //优化4：先判断差值再判断函数，减少函数调用次数 if (flag && ju(k, s, n, a)){ cout << k << endl; break; } } //动态规划完成后需要释放内存 delete[] s; delete[] d; delete[] a; return 0; }