C语言基础

Zstu 2440

Description

在漆黑的夜里，n位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，他们一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，每人所需要的时间分别是a1、a2、...an分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这些人尽快过桥。

Input

输入分2行

第一行是一个整数n(1<=n<=1000)

第二行是n个整数，分别表示这n个人单独过桥需要的时间

Output

输出一行，他们过桥需要的总时间

Sample Input

5

1 3 6 8 12

Sample Output

29

Source

yhr

分析： 刚看到这道题目是是不是觉得很简单呢？其实它并不简单。

这是一个规模比较大的问题，一般来说，我们解决这类问题都会把它归纳为一个个的子问题，进而递推求解。还记得，母牛的那道题目吗？就是这样的。

这个问题同样如此。从比较小的规模来考虑。每次送过两个人，每次的最小时间必然产生在两种情况中：

1.最快的人依次带着剩余最慢的两个一次过桥，用时为a[i]+a[1]+a[i-1]+a[1]，就是说最快的带其中一个先过去，最快的回来，再带下一个过去，再回来；

2.最快的两个人依次带最慢的两个过桥，用时为a[2]+a[1]+a[i]+a[2].也就是说，最快的两个先过桥，其中一个回来，最慢两个过去，剩余的那个回来。

这是在总人数大于等于4的时候才能用，1到3是特殊情况；

另外说一下，我们学校的OJ上数据是错的，它只考虑了第二种情况，所以你只考虑2 的话，就能AC。我这边给出的是正解。交到OJ是WA。

#include #include using namespace std; int main(void){ intn,a[120],i; while(~scanf(\ int sum=0; for(i=1;i<=n;i++) scanf(\ }

sort(a+1,a+n+1);//令用时升序，即速度递减 if(n==1)printf(\ else if(n==2)printf(\ else if(n==3)printf(\，2，3是特殊情况，直接出答案 else{//详情见分析 if(n%2==0){ for(i=n;i>=4;i-=2) sum+=min(2*a[1]+a[i]+a[i-1],a[1]+2*a[2]+a[i]); printf(\ } else{ for(i=n;i>=5;i-=2) sum+=min(2*a[1]+a[i]+a[i-1],a[1]+2*a[2]+a[i]); printf(\ } } }

return 0;

Hdu 1004（杭电的OJ acm.hdu.edu.cn） Problem Description

Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.

This year, they decide to leave this lovely job to you.

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.

A test case with N = 0 terminates the input and this test case is not to be processed.

Output

For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.

Sample Input

5

green red blue red red 3 pink orange pink 0

Sample Output

red pink

Author

WU, Jiazhi

Source

ZJCPC2004

Recommend

JGShining

分析：这道题是我们上学期的期末考试最后一题，其实难度不大，就是输出出现次数最多的元素。详见代码

# include # include int main(void) {

char a[1003][20]; intn,b[1003];

while(scanf(\ {

memset(b,0,sizeof(b));//初始化计数用的b数组 for(int i=1;i<=n;i++) scanf(\

for(int j=1;j

int max=b[1],t=1; for(int i=2;i<=n;i++)

if(b[i]>max){max=b[i],t=i;}//用t记录最大元素的下标 printf(\ } return 0; }

如果以上的题目你都能够弄清楚，能够靠自己做出来的话，你考试绝对不会差。下面有两道练习题，试试能不能做出来。加油！

4050

Description