ALGO1001 礼物
采用的是二分的思想
我感觉用二分的时候就是所找的值在一个区间里面我们就可以采用
二分查找的模板是：
整数二分最后退出的条件是 l = r，所以最终的 l 和 r 是相等的，输出哪个都行。
while (l < r){int mid = l + r >> 1; //(l+r)/2if (check(mid)) r = mid; // check()判断mid是否满足性质else l = mid + 1;} //再往左找目标 //当目标值存在多个时候找的是最左侧的目标值while (l < r){int mid = l + r + 1 >> 1; //(l+r+1)/2if (check(mid)) l = mid;else r = mid - 1;} //在往右找目标 //当目标值有多个时候找到的是最右侧的目标值
像这道题而言答案就在 1到N之间暴力肯定超时
我们用二分来找这个最大值我们要考虑数据的大小来采用不同的数据类型（这个还是很重要的）
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int M = 1e6+5;
int N;long long S;
long long val[M], a[M]; //前缀和，石子每个的质量
bool check(int mid)
{for (int i = mid; i <= N-mid; i++){if (val[i] - val[i - mid] <= S && val[i + mid] - val[i] <= S){return true; //存在符合情况的}}return false;
}
int main()
{cin >> N >> S;for (int i = 1; i <= N; i++){cin >> a[i];val[i] = val[i - 1] + a[i]; //求前缀和}//找符合要求的最大值采用二分法int l = 1, r = N;while (l < r){int mid = l + r + 1 >> 1; //(l+r)/2if (check(mid)){l = mid;}elser = mid - 1;}cout << 2 * l << endl;
}ALGO1001跳马
这个采用的是BFS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
//采用BFS解决走马问题
int vir[8][2] = {
{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}; // 8个方向
bool vis[10][10]; //判断型数组
int a, b, c, d;
typedef struct
{int x, y, temp = 0; //横坐标纵坐标以及步数
} list;
int BFS()
{vis[a][b] = true;queue<list> Q; //用结构体队列list l1;l1.x = a;l1.y = b;Q.push(l1);while (!Q.empty()){list l2 = Q.front();Q.pop(); //出队列for (int i = 0; i < 8; i++){int x = l2.x + vir[i][0];int y = l2.y + vir[i][1];if (1 <= x && x <= 8 && 1 <= y && y <= 8){if (x == c && y == d){cout << ++l2.temp;return 1;}else if (!vis[x][y]){list l3;l3.x = x;l3.y = y;l3.temp = l2.temp + 1;Q.push(l3);vis[x][y]=true;}}}}return -1;
}
int main()
{cin >> a >> b >> c >> d;if(a==c&&b==d){cout<<0<<endl;}else{int B=BFS();if(B==-1){cout<<-1;}}}