#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 20000
int Max(int x, int y, int z, int w)
{
int p, q;
p = max(x, y);
q = max(z, w);
return max(p, q);
}
int main()
{
int n, p[MAXSIZE][3], bridge1, bridge2, m, u, v, x, cnt1, cnt2, cnt3, cnt4, status, result[100000];
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &p[i][0]);
if (p[i][0] == 1) //设置该树对应的花期
{
p[i][1] = 1;
p[i][2] = 3;
}
if (p[i][0] == 2)
{
p[i][1] = 3;
p[i][2] = 4;
}
if (p[i][0] == 3)
{
p[i][1] = 4;
p[i][2] = 5;
}
if (p[i][0] == 4)
{
p[i][1] = 9;
p[i][2] = 10;
}
}
scanf("%d", &bridge1); //获取桥连接的两个点
scanf("%d", &bridge2);
scanf("%d", &m); //获取循环次数
for (int i = 0; i < m; i++)
{
cnt1 = 0; //计数器清0
cnt2 = 0;
cnt3 = 0;
cnt4 = 0;
scanf("%d", &x); //获取该次欣赏的季节
scanf("%d", &u); //获取该次的出发点
scanf("%d", &v); //获取该次的终止点
for (int t = u - 1; t < v; t++) //顺时针不走桥欣赏
{
if (x >= p[t][1] && x <= p[t][2])
cnt1++;
}
for (int t = u + 9; t >= v - 1; t--) //逆时针不走桥欣赏
{
if (x >= p[t % 10][1] && x <= p[t % 10][2])
{
cnt2++;
}
}
if (x >= p[v - 1][1] && x <= p[v - 1][2]) //顺时针走桥欣赏之前先判断终点的树是否开花
cnt3++;
for (int t = u - 1; t != v - 1;) //顺时针走桥欣赏(该循环不记录终点是否开花)
{
status = 0; //设置一开始为顺时针走
if (x >= p[t%10][1] && x <= p[t%10][2])
cnt3++;
if (t == bridge1 - 1) //逻辑位置和存储位置相差1
{
t = bridge2 - 1;
if (t < u && t > v)
{
if (t < u)
t += 10;
status = 1; //若过桥之后的点不在u和v之间,则开始逆时针走
}
}
if (t == bridge2 - 1)
{
t = bridge1 - 1;
if (t < u && t > v)
{
if (t < u)
t += 10;
status = 1; //若过桥之后的点不在u和v之间,则开始逆时针走
}
}
if (status == 0)
t++;
else
t--;
}
result[i] = Max(cnt1, cnt2, cnt3, cnt4);
}
for (int i = 0; i < m; i++)
{
if (result[i] != 0)
printf("%d\n", result[i]);
else
printf("So Sad.\n");
}
return 0;
}
希望大家能在我的代码上面进行改进和补充
我的解题思路是求解每一条路径的开花树的数量,输出最大的那个数量。一共分为四条路径:顺时针不走桥,逆时针不走桥,顺时针走桥,逆时针走桥。目前已经实现了顺时针不走桥的路径和逆时针不走桥的路径,顺时针走桥的代码有问题,逆时针走桥的代码还没写。
希望大家能帮忙看看
#include "stdio.h"
#define MAXSIZE 500001
bool flower(long hua,long season1);
void shun(long head,long tail); // 正向走
void ni(long head,long tail); // 反着走
long N,M,p[MAXSIZE],bridge1,bridge2; // 养成一个习惯,关键循环字符用大写
long season,start,end,flag,result;
int main()
{
// 梅花1 (1-3), 樱花2 (3-4), 石兰花3 (4-5),桂花4 (9-10)
scanf("%ld", &N);
for (long i = 1; i <= N; i++) scanf("%ld", &p[i]); // 每个点花的读入
scanf("%ld %ld %ld", &bridge1,&bridge2,&M); //获取桥连接的两个点,获取查询次数
while (M--)
{
// 欣赏沿途的花不太清楚有没有包括start 跟 end 这俩点
result = flag = 0;
scanf("%ld %ld %ld",&season,&start,&end);
// 顺时针不走桥欣赏
shun(start,end);
result = result>flag ? result : flag;
flag=0;
// 逆时针不走桥欣赏
ni(start,end);
result = result>flag ? result : flag;
flag=0;
// 走桥
int f1=0,f2=0;
if(bridge1>=start && bridge1<end) f1 = 1;
if(bridge2>=start && bridge2<end) f2 = 1;
if(f1+f2==1){ // 桥头一个在里一个在外
long inside = f1==1 ? bridge1 : bridge2; // 在范围内的桥头
long outside = inside==bridge1 ? bridge2 : bridge1; // 在范围外的桥头
// 按start与end分2种情况讨论
if(start<end){ // 出发地编号小于目的地
// 先去 inside
shun(start,inside);
ni(outside,end);
result = result>flag ? result : flag;
flag=0;
// 先去 outside
for(long z=start-1;z!=outside;z--);
ni(start,outside);
shun(inside,end);
result = result>flag ? result : flag;
flag=0;
}else{
// 先去 inside
ni(start,inside);
shun(outside,end);
result = result>flag ? result : flag;
flag=0;
// 先去 outside
shun(start,outside);
ni(inside,end);
result = result>flag ? result : flag;
flag=0;
}
}
if(result) printf("%ld\n",result);
else printf("So Sad.\n");
}
return 0;
}
bool flower(long hua,long season1){
if(hua==1 && season1>=1 && season1<=3 ) return true;
if(hua==2 && season1>=3 && season1<=4 ) return true;
if(hua==3 && season1>=4 && season1<=5 ) return true;
if(hua==4 && season1>=9 && season1<=10) return true;
return false;
}
void shun(long head,long tail){
if(flower(p[head],season)) flag++;
while (head!=tail){
if(head==N) head=0;
head++;
if(flower(p[head],season)) flag++;
}
if(flower(p[tail],season)) flag++;
}
void ni(long head,long tail){
if(flower(p[head],season)) flag++;
while (head!=tail){
head--;
if(head==0) head=N;
if(flower(p[head],season)) flag++;
}
if(flower(p[tail],season)) flag++;
}
关于路径的问题