[Offer收割]编程练习赛4

时间:2023-02-13 17:59:38
[Offer收割]编程练习赛4  题目简单描述和思路简析
  1. 最近天气炎热,小Ho天天宅在家里叫外卖。他常吃的一家餐馆一共有N道菜品,价格分别是A1, A2, ... AN元。并且如果消费总计满X元,还能享受优惠。小Ho是一个不薅羊毛不舒服斯基的人,他希望选择若干道不同的菜品,使得总价在不低于X元的同时尽量低。

    你能算出这一餐小Ho最少消费多少元吗?

    解题思路:这是一道简单的0-1背包问题,该题可以用二维背包,也可以用一维背包,只是在用一维背包时,需要从小枚举到大,详细请看代码。
    
#include <iostream>
#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;

}

2. 

如下图所示,某市市区由M条南北向的大街和N条东西向的道路组成。其中由北向南第i条路和第i+1条路之间的距离是Bi (1 <= i < N),由西向东第i条街和第i+1条街之间的距离是Ai (1 <= i < M)。

[Offer收割]编程练习赛4

小Ho现在位于第x条路和第y条街的交叉口,他的目的地是第p条路和第q条街的交叉口。由于连日降雨,城市中有K个交叉口积水太深不能通行。小Ho想知道到达目的地的最短路径的长度是多少。

 思路详解:

 把每个交点看成图中的一个顶点,每个顶点与相邻顶点连边,形成一个有向图,直接用SPFA(一种求解最短路算法)

#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
#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;
}
3. 

小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;}