2 jian yun rui Jian_Yun_Rui 于 2016.09.12 14:13 提问

acm 总是Time Limit Exceed!!!!!!!!!!!

Description

The 36th ACM match was hosted in Chengdu in 2011 Nov 4. There is an interesting rule in ACM match that once you solve a problem, you'll get a balloon.

To simplify these names, we just name these teams S1, S2, S3 ... SN.

We want to know how many balloons they get between team Si and Sj (including Si and Sj). We may ask many times. It is too boring to count every time.

Since you are a programmer, can you write a program to solve it?

Input

First is an integer N (1 <= N <= 140) indicates the number of schools.

Followed with an integer M (1 <= M <= 50000) indicates the number of operations.

There are two kinds of operations.

AC X

     Means team SX solve a problem and will get a balloon.

COUNT X Y

     Means count balloons of team between SX and SY

Output

For each operation "COUNT X Y" output the number you count

Sample Input
5 4
AC 1
COUNT 1 3
AC 2
COUNT 1 3
Sample Output
1
2

我的程序:
#include
#include
#include
using namespace std;
int main()
{
int b,a;
scanf("%d%d",&b,&a);
int *c=new int[b];
for(int j=0;j {
c[j]=0;
}
while(a--)
{
string d;
int g,p,f;
cin>>d;
if(d=="AC")
{
scanf("%d",&g);
c[g-1]++;
}else if(d=="COUNT")
{
scanf("%d%d",&p,&f);
int sum=0;
for(int i=p-1;i<f;i++)
{
sum+=c[i];
}
printf("%d\n",sum);
}

}
return 0;
}

4个回答

dfsdffe
dfsdffe   2016.09.13 16:14
已采纳

反正闲着没事,就去你们矿业大学的ACM注册了个账户,用java写了一个,你可以参考一下

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            int schools = in.nextInt();// 学校数
            int operations = in.nextInt();// 操作数
            int[] arr = new int[schools + 1];// 数组
            for (int i = 0; i < operations; i++) {
                String oper = in.next();
                if (oper.equals("AC")) {
                    int school = in.nextInt();
                    // 从当前学校往后的所有学校都加一
                    for (int j = school; j < schools + 1; j++) {
                        arr[j]++;
                    }
                } else {
                    int first = in.nextInt();
                    int second = in.nextInt();
                    System.out.println(arr[second] - arr[first - 1]);
                }
            }
        }
    }
}


图片说明

Jian_Yun_Rui
Jian_Yun_Rui   2016.09.12 15:40

为什么会出现这种问题啊

dfsdffe
dfsdffe   2016.09.13 15:42

Time Limit,很明显就是你超时了。每道题都是有空间限制和时间限制的,由于你的算法效率太低,导致运行速度缓慢,就会出现这个错误。

这道题数值那么大,很明显你挨个统计是不行的,而且题里也提示了(It is too boring to count every time.),所以说需要换一种解决思路。

dfsdffe
dfsdffe   2016.09.13 15:49

我觉得这道题的制约应该是在统计上,测试应该是用了很多次统计,所以时间慢。
我有种解决思路是,数组中存的不是该学校的AC数,而是从第一个学校到该学校的AC数。
count的时候,那你用c[sj]-c[si-1]就能得到答案(由于题目要求是包括si和sj)

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!