首页 > ACM题库 > HDU-杭电 > hdu 2600 War-贪心-[解题报告]C++
2014
02-10

hdu 2600 War-贪心-[解题报告]C++

War

问题描述 :

      War is the reciprical and violent application of force between hostile political entities aimed at bringing about a desired political end-state via armed conflict. War is an interaction in which two or more militaries have a “struggle of wills”. When qualified as a civil war, it is a dispute inherent to a given society, and its nature is in the conflict over modes of governance rather than sovereignty. War is not considered to be the same as mere occupation,murder or genocide because of the reciprical nature of the violent struggle, and the organized nature of the units involved.
      War is also a cultural entity, and its practice is not linked to any single type of political organisation or society. Rather, as discussed by John Keegan in his “History Of Warfare”, war is a universal phenomenon whose form and scope is defined by the society that wages it.

      Today we don’t want to talk about war, rather than , I want you to tell me which year there was no war.

输入:

For each test case, first input one integer N(1<= N <= 100), then two integers p and q (-6000000 <= p <= q <= 6000000) represent the starting year and the ending year in this case. Followed by N wars.
Each war described as follows:
Ai Bi Ni (A,B is integer, p <= A, B <= q, Ni is a String which is the ith war’s name )
Represent that the ith War took place between year A and year B.

输出:

For each test case, first input one integer N(1<= N <= 100), then two integers p and q (-6000000 <= p <= q <= 6000000) represent the starting year and the ending year in this case. Followed by N wars.
Each war described as follows:
Ai Bi Ni (A,B is integer, p <= A, B <= q, Ni is a String which is the ith war’s name )
Represent that the ith War took place between year A and year B.

样例输入:

3
100 200
100 120 RtWar
110 140 WeWar
141 199 QqWar 
1
-600 600
-600 600 Cool War

样例输出:

200
Badly!

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct ss
{
 int st,en;
}s[101];
int cmp(ss a,ss b)
{
  if(a.en!=b.en)
  return a.en<b.en;
  else
  a.st<b.st;

}
int main()
{
 int n,i,sum,max,st,en;
 char c[100];
 while(scanf("%d",&n)!=EOF)
 {
  max=-6000001;
   scanf("%d %d",&st,&en);
   for(i=0;i<n;i++)
   {
   scanf("%d %d%*c",&s[i].st,&s[i].en);
   gets(c);
   }
   sort(s,s+n,cmp);
   //for(i=0;i<n;i++)
   //printf("%d fggf %d\n",s[i].st,s[i].en);
   if(s[0].st-st>0)
   max=s[0].st-1;
   for(i=1;i<n;i++)
   {
    if(s[i].st-1<=s[i-1].en)
    {
        s[i].st=s[i-1].st;
    }
     else
      max=s[i].st-1;
   }
   if(s[n-1].en-en<0)
   max=en;
   if(max==-6000001) printf("Badly!\n");
   else printf("%d\n",max);
 }
}

解题转自:http://blog.csdn.net/were__wolf/article/details/9794077


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥