silentboy82

以下是我同学给我做的其中一道题,有谁能时间复杂度为O(N)的算法完成?
我的算法群:5648269(对算法感兴趣的加)
Description

Sher is a financial manager of a big company. He do not like the pay the employees in regular way. So he would like to make his boring job a little bit interesting.

Suppose there are n employees in Sher's company and every one has his own number. The number arrange from 1 to n. There are no two number are the same and no one number in [1,n] will miss.

Sher will give the them money in n days. Everyday he choose the person from an interval [a,b]. The people who has the number within the inteval will be given c dollors. It seems really interesting, eh? But it brings some troubles to treasurers.

Your task is simple: help the treasurers to calculate how much does everyone get.

Input

The input will be several test cases. And every case begins with an integer n(1 < n < =100000) indicate the number of imployees. Then the following n lines contain three integers each. They are a,b and c(c < 1000) respectively and their meaning are as description above. There will be multiple test cases.

Output

Please ouput the total money everyone got in a line divide by white space.

Sample Input


5
2 3 1
1 2 2
4 5 3
1 4 1
1 5 1

Sample Output


4 5 3 5 4

冬天的菠菜

要是你能翻译过来就好多了

silentboy82

好的!我有空翻译一下 !

wuhao628

就是呀！你把它翻译成汉语嘛？

一只人

用空间复杂度为Ｏ（Ｎ）很简单啊，从头到尾搜索就好了，Ｎ单元就是Ｎ个人的工资啊，每搜索到有该人的工资更新Ｎ单元的内容就好了
如果用时间复杂度为Ｏ（Ｎ）就麻烦，不知道题目是不是写错了

chen++

什么啊

silentboy82

我真的写错了也！不好意思啊！是时间复杂度！

xblue

Description描述
sher是一家大公司的经理。他不喜欢用正常的手段方式给他的手下付钱！
Sher is a financial manager of a big company. He do not like the pay the employees in regular way.
So he would like to make his boring job a little bit interesting.
因为这样能给他单调无味的工作添加一点乐趣！
Suppose there are n employees in Sher&#39;s company and every one has his own number.
假设 Sher&#39;s 他们公司有N个雇员，并且每个人都有一个工号（号码），
The number arrange from 1 to n. There are no two number are the same and no one number in [1,n] will miss.
工号从1排到了N，并且工号没有重复也没有遗漏（[1,N]的工号是连续的呵呵！）
Sher will give the them money in n days. Everyday he choose the person from an interval [a,b].
Sher会在N天之内给他的雇员付钱，每一天，他会从一个区间[A,B]选择人（给他付钱）；
The people who has the number within the inteval will be given c dollors. It seems really interesting, eh? But it brings some troubles to treasurers.
被选择（在区间[A,B]的人）的的雇员会得到C美圆。这看起来的确很有趣，呵呵？可是这却给出纳员带来了麻烦！
Your task is simple: help the treasurers to calculate how much does everyone get.
您的任务是简单的：：帮助出纳员计算出，每个人会得到多少的钱？
Input

The input will be several test cases. And every case begins with an integer n(1 < n < =100000) indicate the number of imployees.
输入将会有几种情况！每一种情况都会以一个整数N开始！表明有N个雇员！
Then the following n lines contain three integers each. They are a,b and c(c < 1000) respectively and their meaning are as description above. There will be multiple test cases.
以下的N行包括了３个整数！他们各自为１，２，３
这意味着以上的描述！他们会有许多的情况！
Output
输出
Please ouput the total money everyone got in a line divide by white space.
请将每个人得到的钱用空格分开！写出一行！
Sample Input
简单的输入

5
2 3 1
1 2 2
4 5 3
1 4 1
1 5 1

Sample Output
简单的输出

4 5 3 5 4

以下为广告！http://6cncn.cn
提供blog服务！呵呵特别邀请喜欢java的加入！呵呵

starffly

单循环一次扫描时间复杂度当然是o(N)了
sum[1...total];
for(1...total){
    sum[a...b]+=c;        
}
print(sum[1...total]);

silentboy82

引用:

引用第7楼xblue于2006-06-10 12:31发表的“我来翻译呵呵！不过我的算法刚学”:
Description描述
sher是一家大公司的经理。他不喜欢用正常的手段方式给他的手下付钱！
Sher is a financial manager of a big company. He do not like the pay the employees in regular way.
So he would like to make his boring job a little bit interesting.
因为这样能给他单调无味的工作添加一点乐趣！
.......

谢谢你的翻译了~翻译得挺好的~

silentboy82

引用:

引用第8楼starffly于2006-06-11 09:35发表的“”:
单循环一次扫描时间复杂度当然是o(N)了
sum[1...total];
for(1...total){
    sum[a...b]+=c;        
}
.......

这个算法好象还是超时，时间复杂度不是O（N）
先说一下我对你这个算法的理解不知道是不是正确，
你用一维数组来存储每个员工的工资，
然后再用循环把得到一个区间a,b就该区间的所有员工工资加C。
我以前是这个思路~这样没有严密的算法，只是根据常规思路
因为假设要老板要输入N次（a,b,c)
而且每次的（a,b)都是（1，n)
这样的复杂度就有O（n*n）
超时了，
谢谢你的回复~

silentboy82

我把我同学编的算法贴上~大家可以看看~很不错的思路哦~
/*by naughtyboy*/
#include<stdio.h>
#include<string.h>
int n,a,b,c;
int llist[100000],rlist[100000];
bool left[100000],right[100000];
void solve()
{
  int i,sum=0,temp=0;
  printf("%d",llist[0]);
  sum=llist[0];
  for(i=1;i<n;i++)
  {  
    temp=sum;
    if(right){
      right=0;
      sum+=llist;
      temp=sum;
    }
    if(left){
      left=0;
      sum-=rlist;
    }
    printf(" %d",temp);
  }
  printf("\n");
}
void ini()
{
  memset(llist,0,sizeof(llist));
  memset(rlist,0,sizeof(rlist));
}
int main()
{
  int i;
  while(scanf("%d",&n)==1)
  {
    ini();
    for(i=0;i<n;i++)
    {
      scanf("%d%d%d",&a,&b,&c);
      llist[a-1]+=c;
      rlist[b-1]+=c;
      right[a-1]=1;
      left[b-1]=1;
    }
    solve();
  }
  return 0;
}

thinfost

Sher是一家大公司的一位财政经理。 他不喜欢薪水雇员用规则方式。 如此他希望做他的乏味工作稍微感兴趣。
假设有n雇员在Sher的公司中，并且每一个有他自己的数字。 数字从1安排到n。 没有数字是同一个和没有数字的二[1，n]将错过。
Sher在n天将给他们金钱。 每天他从间隔时间[a选择人，b]。 在inteval之内有数字将给的人民c dollors。 它似乎真正地有趣， 嗯？ 但它给财务官带来一些麻烦。
您的任务是简单的： 帮助财务官计算多少做大家得到。
输入
输入将是几个判例案件。 并且每个案件从整数n (1开始< n < =100000)表明imployees的数量。 然后以下n线包含每个三个整数。 他们是a，b和c (c < 1000)和他们的意思分别为作为描述上面。 将有多个判例案件。
总金钱在线得到的大家由白色空间划分请的产品ouput。
样品输入

starffly

我那种做法是合理的，操作步骤不能少了

silentboy82

合理是合理~
不过超时吗，
就是效率不高，那道题是ACM竞赛题了，追求的是算法的最优效率啊~