? Color the ball

Time Limit: 9000/3000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13667????Accepted Submission(s): 6865


Problem Description N個氣球排成一排，從左到右依次編號為1,2,3....N.每次給定2個整數a b(a <= b),lele便為騎上他的“小飛鴿"牌電動車從氣球a開始到氣球b依次給每個氣球涂一次顏色。但是N次以后lele已經忘記了第I個氣球已經涂過幾次顏色了，你能幫他算出每個氣球被涂過幾次顏色嗎？
Input 每個測試實例第一行為一個整數N,(N <= 100000).接下來的N行，每行包括2個整數a b(1 <= a <= b <= N)。
當N = 0，輸入結束。
Output 每個測試實例輸出一行，包括N個整數，第I個數代表第I個氣球總共被涂色的次數。
Sample Input 3 1 1 2 2 3 3 3 1 1 1 2 1 3 0
Sample Output 1 1 1 3 2 1 這道題和hdu 1166士兵殺敵是相反的，士兵殺敵是 ? ?單點更新 ，求區間和；這道題是 ? 區間更新，求單點值；

正確代碼：

#include<iostream> #include<cstring> #define Size 100010 int N; using namespace std; int c[Size]; int lowbit(int x){return x&(-x); } void add(int i,int x){while(i<=N){c[i]+=x;i+=lowbit(i);} } int Sum(int n) {int sum=0;while(n>0){sum+=c[n];n-=lowbit(n);}return sum; } int main() {int a,b,i,j;while(cin>>N&&N){ memset(c,0,sizeof(c));for(i=0;i<N;i++) //這里不能用while(N--) {cin>>a>>b;add(a,1);add(b+1,(-1)); //更新了區間 }for(i=1;i<N;i++)cout<<Sum(i)<<" ";cout<<Sum(N)<<endl;} }

另一種方法：

此代碼超市，沒改進，O(∩_∩)O哈哈~看到的有興趣，可以改進一下； #include<iostream> #include<cstring> #define Size 100010 int N; using namespace std; int c[Size]; int main() {int a,b,i,j;while(cin>>N&&N){ memset(c,0,sizeof(c));for(i=0;i<N;i++) {cin>>a>>b;for(;a<=b;a++)c[a]++;}for(i=1;i<N;i++)cout<<c[i]<<" ";cout<<c[N]<<endl;} }

總結

以上是生活随笔為你收集整理的Color the ball的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。