2013
11-11

# Unhappy Jinjin

Jinjin is a junior school student. Besides the classes in school, Jinjin’s mother also arranges some supplementary classes for her. However, if Jinjin studies for more than eight hours a day, she will be unhappy on that day. On any day she gets unhappy, the more time she studies, the unhappier she will be. Now we got Jinjin’s class schedule for the next several days and your task is to find out whether she will be unhappy on these days; if she will be unhappy, on which day she will be the unhappiest.

There may be several test cases. In the first line of each test case, there is an integer N (1 <= N <= 7), which represents the number of days you should analyze. Then there comes N lines, each contains two non-negative integers (each smaller than 10). The first integer represents how many hours Jinjin studies at school on the day, and the second represents how many hours she studies in the supplementary classes on the same day.

A case with N = 0 indicates the end of the input, and this case should not be processed.

For each test case, output a line contains a single integer. If Jinjin will always be happy, the integer should be 0; otherwise, the integer should be a positive integer K, which means that Jinjin will be the unhappiest on the K-th day. If the unhappiest day is not unique, just output the earliest one among these unhappiest days.

7
5 3
6 2
7 2
5 3
5 4
0 4
0 6
1
4 4
0


3
0


Here is a sample solution of this problem using C language:
#include <stdio.h>
int main(){
while(1) {
int i, n;
int maxday, maxvalue = -1;
scanf("%d", &n);
if (n == 0) break;
for (i = 1; i <= n; i++) {
int a, b;
scanf("%d%d", &a, &b);
if (a + b > maxvalue) {
maxvalue = a + b;
maxday = i;
}
}
if (maxvalue <= 8) printf("0\n");
else printf("%d\n", maxday);
}
return 0;
}

import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);

int caseNum = 0;
int unhappyDay, unhappyValue;
int studyTime = 0;

while(true)
{
unhappyDay = 0;
unhappyValue = 0;
caseNum = cin.nextInt();

if(caseNum == 0)
break;
else
{
int[][] time = new int[caseNum][2];
for(int i = 0; i < caseNum; i++)
{
for(int j = 0; j < 2; j++)
time[i][j] = cin.nextInt();

studyTime = time[i][0] + time[i][1];
if(studyTime > 8)
{
if(studyTime > unhappyValue)
{
unhappyValue = studyTime;
unhappyDay = i + 1;
}
}

}
System.out.println(unhappyDay);
}
}
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
for (j = adj .begin(); j != adj .end(); ++j)
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？