[Offer收割]编程练习赛4 题目简单描述和思路简析
-
最近天气炎热，小Ho天天宅在家里叫外卖。他常吃的一家餐馆一共有N道菜品，价格分别是A1, A2, ... AN元。并且如果消费总计满X元，还能享受优惠。小Ho是一个不薅羊毛不舒服斯基的人，他希望选择若干道不同的菜品，使得总价在不低于X元的同时尽量低。
你能算出这一餐小Ho最少消费多少元吗？
解题思路：这是一道简单的0-1背包问题，该题可以用二维背包，也可以用一维背包，只是在用一维背包时，需要从小枚举到大，详细请看代码。
#include <iostream>2.
#include <string.h>
#include <string>
using namespace std;
int main()
{
int n,x;
int a[25];
cin >> n >> x;
for(int i = 1;i<=n;i++)
cin >> a[i];
int dp[2005];
memset(dp,0,sizeof(dp));
dp[0] = 1;
for(int i = 1;i<=n;i++)
for(int j = 2000;j>=a[i];j--) //需要从大枚举到小，这样防止一件商品被买多次
dp[j] |= dp[j-a[i]];
int Min = -1;
for(int i = x;i<=2000;i++)
if(dp[i])
{
Min = i;
break;
}
cout << Min << endl;
}
如下图所示，某市市区由M条南北向的大街和N条东西向的道路组成。其中由北向南第i条路和第i+1条路之间的距离是Bi (1 <= i < N)，由西向东第i条街和第i+1条街之间的距离是Ai (1 <= i < M)。
![[Offer收割]编程练习赛4](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0hNNkx5OXRaV1JwWVM1b2FXaHZZMjlrWlhJdVkyOXRMeTl3Y205aWJHVnRYMmx0WVdkbGN5OHlNREUyTURnd055OHhORGN3TlRBek5qazBOVEF6TkM1d2JtYz0%3D.jpg?w=700&webp=1 "[Offer收割]编程练习赛4")
小Ho现在位于第x条路和第y条街的交叉口，他的目的地是第p条路和第q条街的交叉口。由于连日降雨，城市中有K个交叉口积水太深不能通行。小Ho想知道到达目的地的最短路径的长度是多少。
思路详解：
把每个交点看成图中的一个顶点，每个顶点与相邻顶点连边，形成一个有向图，直接用SPFA（一种求解最短路算法）
#include <iostream>3.
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define MAXN 100005
#define MAXM 100005
#define eps 1e-8
typedef long long LL;
using namespace std;
int dis[505][505];
int n,m;
int b[505],a[505];
map<pair<int,int>,int>water;
queue<pair<int,int> >que;
bool judge(int x,int y)
{
if(1 <= x && x <=n && 1 <= y && y <=m)
{
if(water.find(make_pair(x,y))!= water.end())
return false;
return true;
}
return false;
}
void spfa(int start_x,int start_y,int end_x,int end_y)
{
while(!que.empty())
que.pop();
//cout << n << m<<endl;
for(int i = 1; i<=n; i++)
for(int j = 1; j<=m; j++)
dis[i][j] = 100000000;
dis[start_x][start_y] = 0;
que.push(make_pair(start_x,start_y));
int x,y;
while(!que.empty())
{
pair<int,int> tmp = que.front();
que.pop();
x = tmp.first + 1;
y = tmp.second;
if(judge(x,y))
{
if(dis[x][y] > dis[tmp.first][tmp.second] + b[tmp.first])
{
dis[x][y] = dis[tmp.first][tmp.second] + b[tmp.first];
if(!(x == end_x && y == end_y))
que.push(make_pair(x,y));
}
}
x = tmp.first -1;
y = tmp.second;
if(judge(x,y))
{
if(dis[x][y] > dis[tmp.first][tmp.second] + b[tmp.first - 1])
{
dis[x][y] = dis[tmp.first][tmp.second] + b[tmp.first - 1];
if(!(x == end_x && y == end_y))
que.push(make_pair(x,y));
}
}
x = tmp.first;
y = tmp.second + 1;
if(judge(x,y))
{
if(dis[x][y] > dis[tmp.first][tmp.second] + a[tmp.second])
{
dis[x][y] = dis[tmp.first][tmp.second] + a[tmp.second];
if(!(x == end_x && y == end_y))
que.push(make_pair(x,y));
}
}
x = tmp.first;
y = tmp.second - 1;
if(judge(x,y))
{
if(dis[x][y] > dis[tmp.first][tmp.second] + a[tmp.second - 1])
{
dis[x][y] = dis[tmp.first][tmp.second] + a[tmp.second - 1];
if(!(x == end_x && y == end_y))
que.push(make_pair(x,y));
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i<n; i++)
cin >> b[i];
for(int i = 1; i<m; i++)
cin >> a[i];
int Q,x,y,p,q,k;
cin >> k;
for(int i = 0; i<k; i++)
{
cin >> x >> y;
water[make_pair(x,y)] = 1;
}
cin >> Q;
for(int i = 0; i<Q; i++)
{
cin >> x >> y >> p>>q;
spfa(x,y,p,q);
if(dis[p][q] >=100000000)
cout << -1 << endl;
else
cout << dis[p][q] << endl;
/*
for(int i = 1 ;i <= n;i++)
{
for(int j = 1;j<=m;j++)
cout << dis[i][j] << ' ';
cout << endl;
}
*/
}
return 0;
}
小Ho忘了做英语作业，被老师罚抄某段文本N遍。抄写用的作业纸每行包含M个格子，每个格子恰好能填写一个字符或者空格。抄写过程中单词不能跨行，如果某行剩余的格子不足以写完一个单词，那么这个单词需要写在下一行。单词间的空格不能省略。
例如在M=9的作业纸上写2遍"Good good study day day up"：
123456789
Good good
study
day day
up Good
good
study day
day up
小Ho想知道当他抄写完N遍以后，最后一个字符在第几行、第几列。
思路详解：该题对于小数据，直接模拟就行，大约能过40%的数据，对于大数据，需要求循环节。
一 首先把字符串拆分成单词，这有一个小技巧（每个空格都看成一个单词，为了后面好处理），并且在最后加一个空格单词
二 这样最多有101个单词，对于每行肯定是以某一个单词开头，这样当某俩行以同一个单词开头时，就会出现循环，求解出循环节
三 统计求值（该题思路还是挺简单，只是实现比较不好写，涉及到端点的判断，而且题目的结果会超整形，记得要用long long）
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <assert.h>
#include <cmath>
#define eps 1e-8
typedef long long LL;
using namespace std;
int n,m,wordLength,wordNum;
string a;
vector<string>vec;
//表示每个单词第一次出现在开头的行数
int first_occur[105];
//表示到第i行时，字符串循环次数
LL cycle_num[105];
// 找到的循环单词在单词vec中的下标
int cycle_word_id;
// 循环节行数
int cycle_line_num;
// 循环节中字符串循环次数
LL cycle_length;
// 记录每行开头单词在vec中的下标
int line_2_word_id[105];
//对字符串拆分成单词，每个空格看出一个单词
void Split()
{
int start = 0;
while(start < (int)a.length())
{
int i = start;
while(i < (int)a.length() && a[i] != ' ')
i++;
vec.push_back(a.substr(start,i-start));
vec.push_back(string(" "));
start = i + 1;
}
wordNum = vec.size();
}
//返回下一行第一个单词的id，并计算字符串循环的次数
int findFirstWordInLine(int pre_first_word_id,LL preCycle,LL ¤tCycle)
{
int leave_len = m - (int)vec[pre_first_word_id].length();
for(int i= pre_first_word_id + 1;i<wordNum;i++)
{
if(leave_len < (int)vec[i].length())
{
currentCycle = preCycle;
return i;
}
else
leave_len -= (int) vec[i].length();
}
int tmp_cycle_num = leave_len / wordLength;
leave_len -= tmp_cycle_num * wordLength;
currentCycle = preCycle + 1 + tmp_cycle_num;
for(int i = 0;i<wordNum;i++)
{
if(leave_len < (int)vec[i].length())
{
return i;
}
else
leave_len -= (int) vec[i].length();
}
return 0;
}
// 寻找循环节
void cal_cycle()
{
memset(first_occur,-1,sizeof(first_occur));
first_occur[0] = 1;
line_2_word_id[1] = 0;
cycle_num[1] = 1;
LL currentCycle;
for(int i = 2;i<105;i++)
{
int num_id = findFirstWordInLine(line_2_word_id[i-1],cycle_num[i-1],currentCycle);
line_2_word_id[i] = num_id;
if(first_occur[num_id] != -1)
{
cycle_word_id = num_id;
cycle_length = currentCycle - cycle_num[first_occur[num_id]];
cycle_line_num = i - first_occur[num_id];
cycle_num[i] = currentCycle;
line_2_word_id[num_id] = i;
break;
}
else
{
first_occur[num_id] = i;
cycle_num[i] = currentCycle;
}
}
}
// 计算结果
void find_result(LL total_line_num,int line_num,int cycles)
{
int word_id = line_2_word_id[line_num];
int tmp_lines = 0;
for(int i = word_id;i<wordNum;i++)
{
tmp_lines += (int)vec[i].length();
}
tmp_lines += cycles * wordLength;
assert(tmp_lines <= m);
//分析最后一个空格的位置，这个空格不应该计算在内，需要去掉
if(tmp_lines == 1)
{
printf("%lld %d\n",total_line_num + line_num -1,m);
}
else
printf("%lld %d\n",total_line_num + line_num,tmp_lines - 1);
}
int main()
{
cin >> n >> m;
cin.ignore();
getline(cin,a);
wordLength = a.length() + 1;
// 切割单词
Split();
// 计算循环节
cal_cycle();
// 统计最后出现的位置
int i = 1;
for(;i<first_occur[cycle_word_id];i++)
{
if(cycle_num[i + 1] > n)
break;
}
if(i!= first_occur[cycle_word_id])
{
find_result(0,i,n-cycle_num[i]);
}
else
{
//
LL total_line_num = (n-cycle_num[i]) /cycle_length * cycle_line_num;
int j = 1;
int leave_cycle = (n - cycle_num[i])% cycle_length;
for(;j<=cycle_line_num;j++)
if(cycle_num[i + j] - cycle_num[i] >leave_cycle)
break;
find_result(total_line_num,i + j - 1,(leave_cycle - (cycle_num[i + j -1] - cycle_num[i])));
}
return 0;
}
4.
给定一个包含N个整数的数组A。你的任务是将A重新排列，使得任意两个相等的整数在数组中都不相邻。
如果存在多个重排后的数组满足条件，输出字典序最小的数组。
这里字典序最小指：首先尽量使第一个整数最小，其次使第二个整数最小，以此类推。
解题思路：
这是一道构造题：基本解题思路就是每次都拿最小的两个数按顺序的放入数组中，当最后只剩一个数时，但是该数的数量>1,则直接从后往前插入即可。以下代码是另一种解题思路，貌似更复杂一点（看main函数中的注释，思路也挺简单）。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define MAXN 100005
typedef long long LL;
using namespace std;
// mp 统计相同数字的个数
map<int,int>mp;
// 数字值到id的映射
map<int,int>value_2_id;
struct node
{
int value,num;
node(int _value,int _num)
{
value = _value;
num = _num;
}
bool operator < (const node& comp)const
{
if(comp.num > num)
return true;
else if(comp.num == num)
return comp.value < value;
return false;
}
};
// 优先队列，每次取最多元素的个数
priority_queue<node> que;
//num 记录每种数字的个数，Value记录相对应的值，son记录下一个非零元素的下标
int num[MAXN],Value[MAXN],son[MAXN],Ans[MAXN];
void update_priority()
{
while(true)
{
node tmp_node = que.top();
int id = value_2_id[tmp_node.value];
if(tmp_node.num != num[id])
{
tmp_node.num = num[id];
que.pop();
que.push(tmp_node);
}
else
break;
}
}
int find(int id)
{
if(son[id] != id)
return son[id] = find(son[id]);
return id;
}
int main()
{
int n,a;
scanf("%d",&n);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a);
mp[a]++;
}
int id = 0,Max_num = 0;
map<int,int>::iterator ite = mp.begin();
for(;ite!=mp.end();ite++)
{
value_2_id[ite->first] = ++id;
son[id] = id;
que.push(node(ite->first,ite->second));
num[id] = ite->second;
Max_num = max(Max_num,num[id]);
Value[id] = ite->first;
}
/*
printf("outPut Value arr\n");
for(int i = 1;i<=n;i++)
printf("%d ",Value[i]);
printf("\n");
printf("outPut num arr\n");
for(int i = 1;i<=n;i++)
printf("%d ",num[i]);
printf("\n");
*/
if(Max_num *2 > n + 1)
{
printf("-1\n");
return 0;
}
int j = 0,tmp_id;
for(int i = 1;i<=n;i++)
{
while(num[j] == 0)
j++;
//cout << j<< endl;
update_priority();
node Max_num_node = que.top();
if(Max_num_node.num * 2 == n - i + 2) {
// 满足该条件，当前必须插入该值，如果不插入，会导致后面无论怎么排，都会出现相邻的数字值相等 Ans[i] = Max_num_node.value; tmp_id = value_2_id[Max_num_node.value]; num[tmp_id]--; } else if(Ans[i-1] != Value[j]) {
// 选择最小的值进行插入（一种贪心的思路） Ans[i] = Value[j]; num[j]--; tmp_id = j; } else {
// 如果前面是最小值，只能选择剩余中的次小值进行插入 tmp_id = find(j + 1); Ans[i] = Value[tmp_id]; num[tmp_id]--; } //cout << tmp_id << endl; if(num[tmp_id] == 0) son[tmp_id] = son[tmp_id + 1]; } for(int i = 1 ;i< n;i++) printf("%d ",Ans[i]); printf("%d\n",Ans[n]); return 0;}