文章目录
- 试题链接
- 学习笔记-高效算法>排序算法( O(nlogn)时间复杂度 )
- A - Brainman (POJ 1804)
- 中文释义
- 解题分析
- 解题代码
- B - Ultra-QuickSort (POJ 2299, ZOJ 2386, UVA 10810)
- 中文释义
- 解题分析
- 解题代码
- C - Who's in the Middle (POJ 2388)
- 中文释义
- 解题分析
- 解题代码
- D - sort (HDOJ 1425)
- 解题分析
- 解题代码
- E - Word Amalgamation (POJ 1318)
- 中文释义
- 解题分析
- 解题代码
- F - Flooded! (POJ 1877)
- 中文释义
- 解题分析
- 解题代码
- G - Holiday Hotel (POJ 2726)
- 中文释义
- 解题分析
- 解题代码
- H - 排名 (HDOJ 1236)
- 中文释义
- 解题分析
- 解题代码
- I - Election Time (POJ 3664)
- 中文释义
- 解题分析
- 解题代码
试题链接
点我进入代码提交OJ
学习笔记-高效算法>排序算法( O(nlogn)时间复杂度 )
算法介绍
归并排序
主要思路
• 归并排序，是把待排序的序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序的序列。
• 归并排序的算法核心步骤分为两个部分：分解，合并：
- • 首先，把n 个元素分解为n 个长度为1的有序子表；
- • 然后，进行两两归并使元素的关键字有序，得到n/2 个长度为2 的有序子表；
- • 重复上述合并步骤，直到所有元素合并成一个长度为n的有序表 为止。
算法图解
算法代码
整个算法分为分解和合并两个步骤，可用两个函数实现：
- 分解：把n 个元素组成的序列r分解为n 个长度为1的有序子表；
void MergeSort(int r[], int temp[], int s, int t)
{
if(s==t) //分解为长度为1的有序子表
return;
else
{
int m=(s+t)/2;
MergeSort(r, temp, s, m); // 对左边序列进行递归
MergeSort(r, temp, m+1, t); // 对右边序列进行递归
Merge(r, temp, s, m, t); //合并
}
}
- 将数组r的两个连续的有序序列：第s到第m个元素，第m+1到第t个元素，合并产生一个有序序列：第s到第t个元素的有序序列
void Merge(int r[], int temp[], int s, int m, int t)
{
int i=s;
int j=m+1; //i、j：两个连续的有序序列的开始位置
int k=i; //k：临时数组temp的下标
while(i<=m&&j<=t) // 从两个有序序列中取出最小的放入临时数组
if(r[i]<=r[j])
temp[k++]=r[i++];
else
temp[k++]=r[j++];
while(i<=m) // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
temp[k++]=r[i++];
while(j<=t)
temp[k++]=r[j++];
for( i=s; i<=t; i++) // 将临时数组中的内容拷贝回原数组中
r[i]=temp[i];
}
快速排序
主要思路
从数列中挑出一个元素，称为"基准"（pivot）；然后重新排序数列，所有比基准值小的元素放置在基准前面，所有比基准值大的元素放置在基准的后面，和基准相同的元素则可以放置在任何一边。在这个分区结束之后，该基准就处于序列中的某一位置。这一操作称为分区（partition）操作。然后，递归地把小于基准值元素的子序列和大于基准值元素的子序列进行排序。
算法代码
快速分区也可分为 分区与子序列排序 两个步骤，可用两个函数实现：
- 分区操作
Paritition(int A[], int low, int high)
{
int pivot = A[low];
while (low < high)
{
while (low < high && A[high] >= pivot) //从右向左找比pivot小的值
--high;
A[low] = A[high];
while (low < high && A[low] <= pivot) //从左向右找比pivot大的值
++low;
A[high] = A[low];
}
A[low] = pivot; //基准值分区
return low; //返回pivot的位置，作为分界
}
- 快速排序的主函数
void QuickSort(int A[], int low, int high)
{
if (low < high)
{
int pivot = Paritition (A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
十大算法>排序算法的动画演示链接
【十大经典算法>排序算法动画】
【十大经典算法>排序算法（动图演示） + 代码】
C++STL排序函数
使用在C++STL中algorithm里的sort函数，可以对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数进行排序的时间复杂度为O(nlog2n)，sort函数包含在头文件为#include<algorithm>的C++标准库中，其语法为sort (start, end,cmp)，其中start表示要排序数组的起始地址；end表示数组结束地址的下一位；cmp用于规定排序的方法，默认升序。
利用sort函数实现从大到小的排序时，需在cmp加入一个比较函数compare( )。
A - Brainman (POJ 1804)
Background
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.
Problem
Here’s what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:
Start with: 2 8 0 3
swap (2 8) 8 2 0 3
swap (2 0) 8 0 2 3
swap (2 3) 8 0 3 2
swap (8 0) 0 8 3 2
swap (8 3) 0 3 8 2
swap (8 2) 0 3 2 8
swap (3 2) 0 2 3 8
swap (3 8) 0 2 8 3
swap (8 3) 0 2 3 8
So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:
Start with: 2 8 0 3
swap (8 0) 2 0 8 3
swap (2 0) 0 2 8 3
swap (8 3) 0 2 3 8
The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond’s mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.
Input
The first line contains the number of scenarios.
For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.
Output
Start the output for every scenario with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line.
Sample Input
4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0
Sample Output
Scenario #1:
3
Scenario #2:
0
Scenario #3:
5
Scenario #4:
0
中文释义
给出一个N个数字的序列，要求移动这些数字，使得在最后的这一序列是有序的。唯一允许的操作是互换两个相邻的数字。例如：
初始序列：2 8 0 3
互换(2 8) 8 2 0 3
互换(2 0) 8 0 2 3
互换(2 3) 8 0 3 2
互换(8 0) 0 8 3 2
互换(8 3) 0 3 8 2
互换(8 2) 0 3 2 8
互换(3 2) 0 2 3 8
互换(3 8) 0 2 8 3
互换(8 3) 0 2 3 8
这样，序列(2 8 0 3)可以通过9次相邻数字的互换来排序。然而，这一序列也可以用三次互换完成排序：
初始序列：2 8 0 3
互换(8 0) 2 0 8 3
互换(2 0) 0 2 8 3
互换(8 3) 0 2 3 8
因此，本题的问题是：对一个给出的序列进行排序，相邻数字的最小互换次数是多少？请您编写一个计算机程序来回答这个问题。
• 输入
输入的第一行给出测试用例数。
每个测试用例一行，首先给出序列的长度N（1N1000），然后给出序列的N个整数，整数所在的区间为[-1000000, 1000000]。行中的所有数字之间用空格隔开。
• 输出
对每个测试用例，在第一行输出"Scenario #i:"，其中i是从1开始的测试用例编号。然后在下一行给出对给出的序列排序所需的相邻数字的最小互换数。最后，再用一个空行表示测试用例输出结束。
解题分析
对于序列中的一个数，前面大于它的和后面小于它的数的个数，就是该数的逆序对数。一个序列的逆序对数就是该序列的所有数的逆序对数的总和。
本题要求计算，对一个给出的序列进行排序，相邻数字的最小互换次数。也就是要求计算一个序列的逆序对数。
可以用归并排序计算逆序对数，在归并排序中的交换次数就是这个序列的逆序对数：归并排序是将序列a[l, r]分成两个序列a[l, mid]和a[mid+ 1, r]，分别进行归并排序，然后再将这两个有序序列进行归并排序，在归并排序的过程中，设l<=i<=mid，mid+1<=j<=r，当a[i]<=a[j]时，并不产生逆序对数；而当a[i]> a[j]时，则在有序序列a[l, mid]中，在a[i]后面的数都比a[j]大，将a[j]放在a[i]前，逆序对数就要加上mid-i+1。因此，可以在归并排序的合并过程中计算逆序对数。
解题代码
#include<stdio.h>
void MergeSort(int r[], int temp[], int s, int t);
void Merge(int r[], int temp[], int s, int m, int t);
int ans;
int main()
{
int t,n,i,num[1001],temp[1001];
scanf("%d",&t); //输入测试用例数
for(int cc=1;cc<=t;cc++) //每次循环处理一个用例，循环变量即为用例编号
{
if(cc!=1)
printf("\n");
ans=0; //逆序对数初始化
scanf("%d",&n); //输入序列中元素个数
for(i=1;i<=n;i++) //输入序列
scanf("%d",&num[i]);
MergeSort(num,temp,1,n); //归并排序，计算逆序对数
printf("Scenario #%d:\n%d\n",cc,ans); //输出结果
}
return 0;
}
void MergeSort(int r[], int temp[], int s, int t)
{
if(s==t) //分解为长度为1的有序子表
return;
else
{
int m=(s+t)/2;
MergeSort(r, temp, s, m); // 对左边序列进行递归
MergeSort(r, temp, m+1, t); // 对右边序列进行递归
Merge(r, temp, s, m, t); //合并
}
}
void Merge(int r[], int temp[], int s, int m, int t)
{
int i=s;
int j=m+1; //i、j：两个连续的有序序列的开始位置
int k=i; //k：临时数组temp的下标
while(i<=m&&j<=t) // 从两个有序序列中取出最小的放入临时数组
if(r[i]>r[j])
{
temp[k++]=r[j++];
ans+=m+1-i; //累加逆序对数
}
else
temp[k++]=r[i++];
while(i<=m) // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
temp[k++]=r[i++];
while(j<=t)
temp[k++]=r[j++];
for( i=s; i<=t; i++) // 将临时数组中的内容拷贝回原数组中
r[i]=temp[i];
}
B - Ultra-QuickSort (POJ 2299, ZOJ 2386, UVA 10810)
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
中文释义
在本题中，您要分析一个特定的算法>排序算法Ultra-QuickSort。这个算法是将n个不同的整数由小到大进行排序，算法的操作是在需要的时候将相邻的2个数交换。例如，对于输入序列：9 1 0 5 4；Ultra-QuickSort产生输出：0 1 4 5 9。请您算出Ultra-QuickSort 最少需要用到多少次交换操作，才能对输入的序列由小到大排序。
• 输入
输入由若干测试用例组成。每个测试用例第一行给出一个整数n<500,000，表示输入序列的长度。后面的n行每行给出一个整数0≤a[i]≤999,999,999，表示输入序列中第i个元素。输入以n=0为结束，这一序列不用处理。
• 输出
对每个测试用例，输出一个整数，对于输入序列进行排序所作的交换操作的最少次数。
解题分析
对于本题，如果用两重循环枚举序列的每个数对(Ai，Aj)，其中i<j，检验Ai是否大于Aj，然后统计逆序对数。这种算法虽然简洁，时间复杂度为O(n2)，由于本题的输入序列的长度n<500,000，当n很大时，相应的程序出解非常慢。
所以，本题和上一题【A - Brainman】一样，利用时间复杂度为O(nlog2n)的归并排序求逆序对数。
解题代码
#include<stdio.h>
void merge(int a[],int low,int mid,int high);
void merge_sort(int a[],int low,int high);
int a[500000],temp[500000];
long long int ans;
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF && n)
{
ans=0;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
merge_sort(a,1,n);
printf("%lld\n",ans);
}
return 0;
}
void merge(int a[],int low,int mid,int high)
{
int i,j,k;
i=low,j=mid+1,k=low;
while(i<=mid && j<=high)
if(a[i]>a[j])
{
temp[k++]=a[j++];
ans+=mid+1-i;
}
else
temp[k++]=a[i++];
while(i<=mid)
temp[k++]=a[i++];
while(j<=high)
temp[k++]=a[j++];
for(i=low;i<=high;i++)
a[i]=temp[i];
}
void merge_sort(int a[],int low,int high)
{
if(low < high)
{
int mid=(low+high)/2;
merge_sort(a,low,mid);
merge_sort(a,mid+1,high);
merge(a,low,mid,high);
}
}
C - Who’s in the Middle (POJ 2388)
FJ is surveying his herd to find the most average cow. He wants to know how much milk this ‘median’ cow gives: half of the cows give as much or more than the median; half give as much or less.
Given an odd number of cows N (1 <= N < 10,000) and their milk output (1…1,000,000), find the median amount of milk given such that at least half the cows give the same amount of milk or more and at least half give the same or less.
Input
* Line 1: A single integer N
* Lines 2…N+1: Each line contains a single integer that is the milk output of one cow.
Output
* Line 1: A single integer that is the median milk output.
Sample Input
5
2
4
1
3
5
Sample Output
3
Hint
INPUT DETAILS:
Five cows with milk outputs of 1…5
OUTPUT DETAILS:
1 and 2 are below 3; 4 and 5 are above 3.
中文释义
该题上一次做过，中文释义参照上文，此处主要利用快速排序和排序函数进行重做本题！
解题分析
参照快速排序C语言程序段，对输入的产奶量序列进行快速排序，然后输出中点的产奶量。
也可以使用在C++ STL中algorithm里的sort函数，递增排序N头奶牛的产奶量，然后输出中点的产奶量。
注：在参考程序中，sort函数没有第三个参数，实现的是从小到大(升序)排列(默认)。
解题代码
#include<stdio.h>
#define N 100005
void quick_sort(int low,int high);
int partition(int low,int high);
int num[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
scanf("%d",&num[i]);
quick_sort(0,n-1);
printf("%d\n",num[n/2]);
}
return 0;
}
int partition(int low,int high)
{
int i=low,j=high,pivot=num[low];
while(i<j)
{
while(i<j && num[j]>=pivot)
j--;
int t=num[i];
num[i]=num[j];
num[j]=t;
while(i<j && num[i]<=pivot)
i++;
t=num[i];
num[i]=num[j];
num[j]=t;
}
return i;
}
void quick_sort(int low,int high)
{
if(low<high)
{
int x=partition(low,high);
quick_sort(low,x-1);
quick_sort(x+1,high);
}
}
- C++STL(sort函数)
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int n,i;
int cow[10001];
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
cin >> cow[i];
sort(cow,cow+n);
cout << cow[n/2] << endl;
}
return 0;
}
D - sort (HDOJ 1425)
给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
Output
对每组测试数据按从大到小的顺序输出前m大的数。
Sample Input
5 3
3 -35 92 213 -644
Sample Output
213 92 3
Hint
请用VC/VC++提交
解题分析
对n个数进行排序，然后输出前m个大的数。由于数据规模很大，采用时间复杂度为O(n2)的算法>排序算法有可能会超时。所以本题采用快速排序或排序函数来对n个数进行排序。
解题代码
#include<iostream>
using namespace std;
void quick_sort(int low,int high);
int partition(int low,int high);
int num[1000000];
int main()
{
int m,n,i;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<n;i++)
scanf("%d",&num[i]);
quick_sort(0,n-1);
for(i=0;i<m-1;i++)
printf("%d ",num[i]);
printf("%d\n",num[i]);
}
return 0;
}
int partition(int low,int high)
{
int i=low,j=high,pivot=num[low];
while(i<j)
{
while(i<j && num[j]<=pivot)
j--;
int t=num[i];
num[i]=num[j];
num[j]=t;
while(i<j && num[i]>=pivot)
i++;
t=num[i];
num[i]=num[j];
num[j]=t;
}
return i;
}
void quick_sort(int low,int high)
{
if(low<high)
{
int x=partition(low,high);
quick_sort(low,x-1);
quick_sort(x+1,high);
}
}
- C++STL(sort函数)
#include<iostream>
#include<algorithm>
int cmp(int a,int b);
using namespace std;
int num[1000000];
int main()
{
int m,n,i;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<n;i++)
scanf("%d",&num[i]);
sort(num,num+n,cmp);
for(i=0;i<m-1;i++)
printf("%d ",num[i]);
printf("%d\n",num[i]);
}
return 0;
}
int cmp(int a,int b)
{
return a>b;
}
E - Word Amalgamation (POJ 1318)
In millions of newspapers across the United States there is a word game called Jumble. The object of this game is to solve a riddle, but in order to find the letters that appear in the answer it is necessary to unscramble four words. Your task is to write a program that can unscramble words.
Input
The input contains four parts: 1) a dictionary, which consists of at least one and at most 100 words, one per line; 2) a line containing XXXXXX, which signals the end of the dictionary; 3) one or more scrambled ‘words’ that you must unscramble, each on a line by itself; and 4) another line containing XXXXXX, which signals the end of the file. All words, including both dictionary words and scrambled words, consist only of lowercase English letters and will be at least one and at most six characters long. (Note that the sentinel XXXXXX contains uppercase X’s.) The dictionary is not necessarily in sorted order, but each word in the dictionary is unique.
Output
For each scrambled word in the input, output an alphabetical list of all dictionary words that can be formed by rearranging the letters in the scrambled word. Each word in this list must appear on a line by itself. If the list is empty (because no dictionary words can be formed), output the line “NOT A VALID WORD” instead. In either case, output a line containing six asterisks to signal the end of the list.
Sample Input
tarp
given
score
refund
only
trap
work
earn
course
pepper
part
XXXXXX
resco
nfudre
aptr
sett
oresuc
XXXXXX
Sample Output
score
******
refund
******
part
tarp
trap
******
NOT A VALID WORD
******
course
******
中文释义
在美国的很多报纸上，有一种单词游戏Jumble。这一游戏的目的是解字谜，为了找到答案中的字母，就要整理4个单词。请您编写一个整理单词的程序。
• 输入
输入包含4个部分：1）字典，包含至少1个至多100个的单词，每个单词一行；2）一行内容为XXXXXX，表示字典结束；3）一个或多个你要整理的“单词”；4）一行内容为XXXXXX，表示文件的结束。所有的单词，无论是字典单词还是要整理的单词，都是小写英文字母，至少1个字母，至多6个字母（XXXXXX是由大写的X组成），字典中单词不排序，但每个单词只出现一次。
• 输出
对于输入中每个要整理的单词，输出在字典里存在的单词，单词的字母排列可以不同，如果在字典中找到不止一个单词对应时要把他们按字典序进行排序。每个单词占一行。如果没找到相对应的单词则输出NOT A VALID WORD，每输出对应的一组单词或NOT A VALID WORD后要输出******。
解题分析
设字典表示为字符数组word。在字典被输入后，字典word就被建立了。然后，对于每个在word中的单词word [i]，通过选择排序，完成word的字典序排列。
接下来，依次输入待处理的单词，每输入一个单词，存入字符串str，通过sort函数，对其按字符升序进行排序；然后和word中的单词word[i]逐个比较：word[i]也通过sort函数按字符升序进行排序，如果两者相等，则输出word [i]；比较结束时，没有相等的情况，则输出"NOT A VALID WORD"。
在参考程序中，字符串比较函数strcmp按字典序比较两个字符串，并返回结果：如果两个字符串相等，则返回零；字符串复制函数strcpy则是将源字符串变量的内容复制到目标字符串变量中。
解题代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
char word[101][10],str[10],str1[10];
int i,j,len1,len2,s=0;
while(1)
{
scanf("%s",word[s]);
if(strcmp(word[s++],"XXXXXX") == 0)
break;
}
for(i=0;i<s-2;i++)
for(j=i+1;j<s-1;j++)
if(strcmp(word[i],word[j])>0)
{
strcpy(str,word[i]);
strcpy(word[i],word[j]);
strcpy(word[j],str);
}
while(scanf("%s",str)!=EOF && strcmp(str,"XXXXXX")!=0)
{
int flag=1;
len1=strlen(str);
sort(str,str+len1);
for(i=0;i<s-1;i++)
{
len2=strlen(word[i]);
strcpy(str1,word[i]);
sort(str1,str1+len2);
if(strcmp(str1,str)==0)
{
printf("%s\n",word[i]);
flag=0;
}
}
if(flag)
printf("NOT A VALID WORD\n");
printf("******\n");
}
return 0;
}
F - Flooded! (POJ 1877)
To enable homebuyers to estimate the cost of flood insurance, a real-estate firm provides clients with the elevation of each 10-meter by 10-meter square of land in regions where homes may be purchased. Water from rain, melting snow, and burst water mains will collect first in those squares with the lowest elevations, since water from squares of higher elevation will run downhill. For simplicity, we also assume that storm sewers enable water from high-elevation squares in valleys (completely enclosed by still higher elevation squares) to drain to lower elevation squares, and that water will not be absorbed by the land.
From weather data archives, we know the typical volume of water that collects in a region. As prospective homebuyers, we wish to know the elevation of the water after it has collected in low-lying squares, and also the percentage of the region’s area that is completely submerged (that is, the percentage of 10-meter squares whose elevation is strictly less than the water level). You are to write the program that provides these results.
Input
The input consists of a sequence of region descriptions. Each begins with a pair of integers, m and n, each less than 30, giving the dimensions of the rectangular region in 10-meter units. Immediately following are m lines of n integers giving the elevations of the squares in row-major order. Elevations are given in meters, with positive and negative numbers representing elevations above and below sea level, respectively. The final value in each region description is an integer that indicates the number of cubic meters of water that will collect in the region. A pair of zeroes follows the description of the last region.
Output
For each region, display the region number (1, 2, …), the water level (in meters above or below sea level) and the percentage of the region’s area under water, each on a separate line. The water level and percentage of the region’s area under water are to be displayed accurate to two fractional digits. Follow the output for each region with a blank line.
Sample Input
3 3
25 37 45
51 12 34
94 83 27
10000
0 0
Sample Output
Region 1
Water level is 46.67 meters.
66.67 percent of the region is under water.
中文释义
为了让购房者能够估计需要多少的水灾保险，一家房地产公司给出了在顾客可能购买房屋的地段上每个10M*10M的区域的高度。由于高处的水会向低处流，雨水、雪水或可能出现的洪水将会首先积在最低高度的区域中。为了简单起见，我们假定在较高的区域中的积水（即使完全被更高的区域所包围）能完全排放到较低的区域中，并且水不会被地面吸收。
从天气数据我们可以知道一个地段的积水量。作为购房者，我们希望能够得知积水的高度和该地段完全被淹没的区域的百分比（指该地段中高度严格低于积水高度的区域的百分比）。请编写一个程序以给出这些数据。
• 输入
输入数据包含了一系列的地段的描述。每个地段的描述以一对整型数m，n开始，m，n不大于30，分别代表横向和纵向上按10M划分的块数。紧接着m行每行包含n个数据，代表相应区域的高度。高度用米来表示，正负号分别表示高于或低于海平面。每个地段描述的最后一行给出该地段积水量的立方数。最后一个地段描述后以两个0代表输入数据结束。
• 输出
对每个地段，输出地段的编号、积水的高度、积水区域的百分比，每项内容为单独一行。积水高度和积水区域百分比均保留两位小数。每个地段的输出之后打印一个空行。
解题分析
解题代码
#include<algorithm>
#include<iostream>
#define MAX 900
using namespace std;
int main()
{
int i,c,m,n,cases=0;
double v,a[MAX];
while(scanf("%d %d",&m,&n) && (m+n))
{
for(i=0;i<m*n;i++)
scanf("%lf",&a[i]);
scanf("%lf",&v);
sort(a,a+m*n);
i=0;
while(i<m*n-1)
{
if(v<(a[i+1]-a[i])*100*(i+1))
break;
v-=(a[i+1]-a[i])*100*(i+1);
i++;
}
double per,leve;
per=100.0*(i+1)/(m*n);
leve=v/(100*(i+1))+a[i];
printf("Region %d\nWater level is %.2lf meters.\n%.2lf percent of the region is under water.\n",++cases,leve,per);
}
return 0;
}
G - Holiday Hotel (POJ 2726)
Mr. and Mrs. Smith are going to the seaside for their holiday. Before they start off, they need to choose a hotel. They got a list of hotels from the Internet, and want to choose some candidate hotels which are cheap and close to the seashore. A candidate hotel M meets two requirements:
Any hotel which is closer to the seashore than M will be more expensive than M.
Any hotel which is cheaper than M will be farther away from the seashore than M.
Input
There are several test cases. The first line of each test case is an integer N (1 <= N <= 10000), which is the number of hotels. Each of the following N lines describes a hotel, containing two integers D and C (1 <= D, C <= 10000). D means the distance from the hotel to the seashore, and C means the cost of staying in the hotel. You can assume that there are no two hotels with the same D and C. A test case with N = 0 ends the input, and should not be processed.
Output
For each test case, you should output one line containing an integer, which is the number of all the candidate hotels.
Sample Input
5
300 100
100 300
400 200
200 400
100 500
0
Sample Output
2
中文释义
Smith夫妇要去海边渡假，在他们出发前，他们要选择一家宾馆。他们从互联网上获得了一份宾馆的列表，要从中选择一些既便宜又离海滩近的侯选宾馆。侯选宾馆M要满足两个需求：
- 离海滩比M近的宾馆要比M贵。
- 比M便宜的宾馆离海滩比M远。
• 输入
有若干组测试用例，每组测试用例的第一行给出一个整数N（1≤N≤10000），表示宾馆的数目，后面的N行每行给出两个整数D和C（1≤D, C≤10000），用于描述一家宾馆，D表示宾馆距离海滩的距离，C表示宾馆住宿的费用。本题设定没有两家宾馆有相同的D和C。用N = 0表示输入结束，对这一测试用例不用进行处理。
• 输出
对于每个测试用例，输出一行，给出一个整数，表示所有的侯选宾馆的数目。
解题分析
设宾馆序列为h，宾馆用结构表示，其中第i家宾馆离海滩的距离为h[i].dist，住宿费用为h[i].cost。根据侯选宾馆的需求，以离海滩距离为第1关键字、住宿费用为第2关键字，对结构数组h进行排序。然后，在此基础上计算侯选宾馆的数目ans：
对于已经排序的结构数组h，根据题意，如果宾馆a的dist比宾馆b小，那么b的cost一定要比a的cost小，这样b才能作为候选宾馆，以此，依次扫描每家宾馆：若当前宾馆i虽然离海滩的距离不近但费用低，则宾馆i进入候选序列，ans++。最后输出侯选宾馆的数目ans。
解题代码
#include<algorithm>
#include<iostream>
using namespace std;
#define MAX 10000
struct hotel
{
int dist,cost;
}h[MAX];
bool com(const hotel& a,const hotel& b)
{
if(a.dist==b.dist)
return a.cost<b.cost;
return a.dist<b.dist;
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
int i;
for(i=0;i<n;i++)
scanf("%d%d",&h[i].dist,&h[i].cost);
sort(h,h+n,com);
int min=INT_MAX;
int ans=0;
for(i=0;i<n;i++)
if(h[i].cost<min)
{
ans++;
min=h[i].cost;
}
printf("%d\n",ans);
}
return 0;
}
H - 排名 (HDOJ 1236)
今天的上机考试虽然有实时的Ranklist，但上面的排名只是根据完成的题数排序，没有考虑
每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分数线的
考生，并将他们的成绩按降序打印。
Input
测试输入包含若干场考试的信息。每场考试信息的第1行给出考生人数N ( 0 < N
< 1000 )、考题数M ( 0 < M < = 10 )、分数线（正整数）G；第2行排序给出第1题至第M题的正整数分值；以下N行，每行给出一
名考生的准考证号（长度不超过20的字符串）、该生解决的题目总数m、以及这m道题的题号
（题目号由1到M）。
当读入的考生人数为0时，输入结束，该场考试不予处理。
Output
对每场考试，首先在第1行输出不低于分数线的考生人数n，随后n行按分数从高
到低输出上线考生的考号与分数，其间用1空格分隔。若有多名考生分数相同，则按他们考
号的升序输出。
Sample Input
4 5 25
10 10 12 13 15
CS004 3 5 1 3
CS003 5 2 4 1 3 5
CS002 2 1 2
CS001 3 2 3 5
1 2 40
10 30
CS001 1 2
2 3 20
10 10 10
CS000000000000000001 0
CS000000000000000002 2 1 2
0
Sample Output
3
CS003 60
CS001 37
CS004 37
0
1
CS000000000000000002 20
Hint
Huge input, scanf is recommended.
中文释义
提示：海量输入，推荐使用scanf。
解题分析
设考生序列为stu，考生用结构表示，其中字符数组name表示考号，num表示解决的题目总数，sum表示分数。
首先，在输入每个考生信息的时候，根据解题的题号，统计考生的分数。然后结构体排序，分数和考号分别为第一和二关键字。最后，按题目要求输出不低于分数线的考生人数，以及分数线上的考生信息。
解题代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1005;
int que[15];
struct node
{
char name[25];
int num,sum;
}stu[N];
bool cmp(const node &a,const node &b)
{
if(a.sum==b.sum)
return strcmp(a.name,b.name)<0?1:0;
return a.sum>b.sum;
}
int main()
{
int stu_num,test,line,a,cnt;
while(~scanf("%d",&stu_num) && stu_num)
{
cnt=0;
int i;
scanf("%d%d",&test,&line);
for(i=1;i<=test;i++)
scanf("%d",&que[i]);
for(i=1;i<=stu_num;i++)
{
stu[i].sum=0;
scanf("%s%d",stu[i].name,&stu[i].num);
while(stu[i].num--)
{
scanf("%d",&a);
stu[i].sum+=que[a];
}
if(stu[i].sum>=line)
cnt++;
}
sort(stu+1,stu+1+stu_num,cmp);
printf("%d\n",cnt);
for(i=1;i<=stu_num;i++)
{
if(stu[i].sum>=line)
printf("%s %d\n",stu[i].name,stu[i].sum);
else break;
}
}
return 0;
}
I - Election Time (POJ 3664)
The cows are having their first election after overthrowing the tyrannical Farmer John, and Bessie is one of N cows (1 ≤ N ≤ 50,000) running for President. Before the election actually happens, however, Bessie wants to determine who has the best chance of winning.
The election consists of two rounds. In the first round, the K cows (1 ≤ K ≤ N) cows with the most votes advance to the second round. In the second round, the cow with the most votes becomes President.
Given that cow i expects to get Ai votes (1 ≤ Ai ≤ 1,000,000,000) in the first round and Bi votes (1 ≤ Bi ≤ 1,000,000,000) in the second round (if he or she makes it), determine which cow is expected to win the election. Happily for you, no vote count appears twice in the Ai list; likewise, no vote count appears twice in the Bi list.
Input
* Line 1: Two space-separated integers: N and K
* Lines 2…N+1: Line i+1 contains two space-separated integers: Ai and Bi
Output
* Line 1: The index of the cow that is expected to win the election.
Sample Input
5 3
3 10
9 2
5 6
8 4
6 5
Sample Output
5
中文释义
解题分析
解题代码
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 50010
int n,k;
struct node
{
int a,b,num;
}cow[MAX];
int cmpa(node p,node q)
{
if(p.a == q.a)
return p.b>q.b;
return p.a>q.a;
}
int cmpb(node p,node q)
{
if(p.b==q.b)
return p.a>q.a;
return p.b>q.b;
}
int main()
{
int i;
while(~scanf("%d%d",&n,&k))
{
for(i=0;i<n;i++)
{
scanf("%d%d",&cow[i].a,&cow[i].b);
cow[i].num=i+1;
}
sort(cow,cow+n,cmpa);
sort(cow,cow+k,cmpb);
printf("%d\n",cow[0].num);
}
return 0;
}
