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   2016.09.13 16:14

``````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   2016.09.12 15:40

dfsdffe   2016.09.13 15:42

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

dfsdffe   2016.09.13 15:49

count的时候，那你用c[sj]-c[si-1]就能得到答案（由于题目要求是包括si和sj）