本文主要是介绍POJ3258 二分初步/奶牛跳河 ZOJ4033 省赛-.-，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*
二分的是后面的答案 因为数据不是很大
二分就是后面逐步逼近数据范围 最后得到什么
再具体一点的话 这个题想求的是什么?是之间的最小距离
二分的恐怖之处就在于它 O(nlogn的复杂度).【adds】
【adds】
简化着 简化着 没了。。。
首先需要判断 那么就是实验一下去掉哪几个点 judege(n)就可以了
那么这个长度 也就是最后我们想得到的答案 不断的再往下减少
复杂度没高 完了呀
那么judge呢
你可以这样 那么为什么不珍惜你拥有的一切呢
时间原因 关于二分可能还会再详细讲一次
就是有个小问题就是b[i]是重新开的 因为a[i]变了一次就被改变了呀问题不大!...还有可能就是1到n那边,因为要用到边界0和n的值嘛
【又及，是0到n哦，不是a[i]-a[n]...这样的会有999这样直接break的情况】
还有,就是啥,!state和state=!state;......前面那个没用啊...
竟然过了,也是很感动啦
*/
地址https://cn.vjudge.net/problem/POJ-3258#author=ChineseOJ
#include<iostream>
#include<algorithm>
using namespace std;int n, m;int b[50005];
int a[50005];
int k;
int judge(int mid) {int sum = 0;int temp;b[0] = 0; b[k + 1] = n;for (int i = 1; i <= k+1; i++){b[i] = a[i];temp = b[i] - b[i - 1];if (temp >= mid);else {sum++;b[i] = b[i - 1];}}if (sum <= m)return true;else return false;
}int main()
{while (cin >> n>>k >> m) {int ans = 0;for (int i = 1; i <= k; i++) {cin >> a[i];}a[k+1] = n; a[0] = 0;int l = 1; int r = n;sort(a + 1, a + 1+ k);//if (judge(4) == true)cout << " " << endl;while (r-l>1) {int mid = (l + r) / 2;if (judge(mid) == false){r = mid;}elsel=mid;}if (judge(r))cout << r << endl;else cout <<r- 1 << endl;//cout << ans << endl;}return 0;
}另:
???男孩女孩的那个,只要把123456789是奇数的时候反过来就好了,还没看大神的代码,但是难得自己写个题吧....
http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5759
===m=更新 18.5.6====
啊啊啊,大神的代买拉唉了....
没有代码(打脸),但是其实完全不用这么想
比如说吧,
1 2 3 4 这
1 2 3 4 5不行
1 2 3 4 5 6不行
1 2 3 4 5 6 7 可以
1 2 3 4 5 6 7 8可以
1 2 3 4 5 6 7 8 9不行
1 2 3 4 5 6 7 8 9 10不行
1 2 3 4 5 6 7 8 9 ` 10 11可以
就是多了个奇数,再来个奇数也补不上啊-.-
也就是说其实,只要sum是偶数,那么其实可以了
因为任何一个串都可以被表示成和的形式.....只是大小和选取而已,比如说这些sum,sum-1的话只要去掉那个1就可以了,sum-2的话去掉第二个就可以了,sum-3,...直到最大 的a[i]+1 什么的,反正往后加
然后就是不不用这么麻烦的想,只要倒着取就可以了,你要取的那个数,如果大就扔了,小或者没满足就加进去,最后的结果肯定 是满足的
#include <iostream>
#include <algorithm>
#include<string>
using namespace std;
char a[100005];
//struct node {
// char a;
// int value;
//}q[10005];
int main() {int t; cin >> t;while (t--) {int n; cin >> n;int sum = 0;for (int i = 1; i <= n; i++){cin >> a[i];sum+=i;}if (sum % 2 == 1)cout << "-1";// << endl;else if (n % 2 == 0) {for (int i = 1; i <= n/4; i++) {if (a[i] == '0')cout << "1";else if (a[i] == '1')cout << "3";}for (int i = n/4+1; i <= n/2+n/4; i++) {if (a[i] == '0')cout << "2";else if (a[i] == '1')cout << "4";}for (int i = n / 4 + n / 2 + 1; i <= n; i++) {if (a[i] == '0')//如果是女生 就给1cout << "1";else if (a[i] == '1')cout << "3";}}else if (n % 2 == 1){int state = 0;//19 10 for (int i = 1; i <= n; i++){if (state == 0) {if (a[i] == '0')//如果是女生 就给1cout << "1";else if (a[i] == '1')cout << "3";}else {if (a[i] == '0')//如果是女生 就给1cout << "2";else if (a[i] == '1')cout << "4";}if (i == (n - 1) / 2)state=!state;state=!state;}}cout << endl;}return 0;
}
这篇关于POJ3258 二分初步/奶牛跳河 ZOJ4033 省赛-.-的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
