网易笔试8.8前三题

1.输入一组字符串 返回其最短回文字符串

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
bool check(char* ch1);
int main(void)
{
	char ch1[MAXSIZE];
	scanf("%s", ch1);
	int copy ;
	int curlen = strlen(ch1);
	for (copy = 0; !check(ch1); copy++)
	{
		for (int i = copy; i >= 0; i--)
		{
			ch1[curlen + copy - i] = ch1[i];
		}
		ch1[curlen+copy+1] = '\0';
	}
	printf("%s",ch1);
	return 0;
}
bool check(char* ch1)
{
	int left = 0, right = strlen(ch1) - 1;
	while (left < right)
	{
		if (ch1[left] != ch1[right])
			return false;
		left++;
		right--;
	}
	return true;
}

2.n个物品，每个物品有1个价值，分给两人 要求两个人总价值相同 最少扔掉多少价值的物品才能满足要求

/*dfs+剪枝*/
/*每个礼物有三种可能 要么 给A 要么 给B 要么丢掉 */
#include<stdio.h>
#define maxsize 15
void dfs(int* gift, int count, int* result, int n,int value1,int value2);
int max(int a, int b);
int main(void)
{
	int n;//礼物个数
	scanf("%d",&n);
	int gift[maxsize];
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &gift[i]);
		sum += gift[i];
	}
	int result = 0;
	dfs(gift, 0, &result, n, 0, 0);
	result = sum - result;
	printf("%d",result);
	return 0;
}
void dfs(int* gift, int count, int* result, int n,int value1,int value2)
{
	/*终止条件*/
	if (count == n)
	{
		if (value1 == value2)
			*result = max(*result, value1 * 2);
		return;
	}
	/*做选择*/
	for (int i = 0; i < 3; i++)
	{
		if (i == 0)//给A
			value1 += gift[count];
		else if (i == 1)//给 B
			value2 += gift[count];
		dfs(gift, count + 1, result, n, value1, value2);
		/*撤销选择*/
		if (i == 0)
			value1 -= gift[count];
		else if(i == 1)
			value2 -= gift[count];
	}
}
int max(int a, int b)
{
	return a > b ? a : b;
}

3.n个人排队买票 两种买票方式

1.单独买票

2.与后面的人一起买票

卖票员早上八点卖票 最早几点能卖完票

#include<stdio.h>
#define maxsize 2000
int min(int a, int b);
int main(void)
{
	int t;
	int a[maxsize];
	int b[maxsize];
	scanf("%d",&t);
	for (int i = 0; i < t; i++)
	{
		int n;
		scanf("%d",&n);
		for (int i = 0; i < n; i++)
			scanf("%d",&a[i]);
		for (int i = 0; i < n - 1; i++)
			scanf("%d", &b[i]);
		int dp[maxsize];
		/*初始化*/
		dp[0] = 0;
		dp[1] = a[0];
		for (int i = 2; i <= n; i++)
		{
			dp[i] = min(dp[i - 1] + a[i - 1], dp[i - 2] + b[i - 2]);
		}
		int hour, minute,second;
		hour = dp[n] / 3600;
		dp[n] = dp[n] % 3600;
		minute = dp[n] / 60;
		second = dp[n] % 60;
		if (8 + hour > 12)
		{
			hour = 8 + hour - 12;
			printf("%02d:%02d:%02d pm", hour, minute, second);
		}
		else
			printf("%02d:%02d:%02d am", 8+hour, minute, second);
		printf("\n");
	}
	return 0;
}
int min(int a, int b)
{
	return a < b ? a : b;
}