NOIP2011解題報(bào)告
馬鞍山第二中學(xué) 鄭逸寧
DAY1.
1.1carpet
題目簡(jiǎn)述：
求最后一次覆蓋某一點(diǎn)的矩形的序號(hào).
分析:
對(duì)于點(diǎn)（x,y）和矩形（a,b,g,k）,若滿足a<=x<=a+g && b<=y<=b+k,則稱該矩形覆蓋該點(diǎn).
實(shí)現(xiàn)1：
從前向后查找,一邊讀一邊更新.T=O(n),S=O(1);
實(shí)現(xiàn)2：
先存儲(chǔ)下來(lái),從后往前查找,查找到即輸出.T=O(n),S=O(n);
總結(jié)：
一般來(lái)說(shuō),實(shí)現(xiàn)2在數(shù)據(jù)已經(jīng)儲(chǔ)存好的情況下比1要快,但就本題來(lái)說(shuō)比1花費(fèi)了更多的空間,這體現(xiàn)了時(shí)間和空間的辯證關(guān)系.
代碼
#include<cstdio>
#include<cstring>
#include<iostream>
long const maxn=10001;
long a[maxn],b[maxn],x[maxn],y[maxn];
long n;
long ansx,ansy;
bool flag=false;
int main(){
freopen("carpet.in","r",stdin);
freopen("carpet.out","w",stdout);
scanf("%ld",&n);
for(int i=1;i<=n;i++)
scanf("%ld %ld %ld %ld",&a[i],&b[i],&x[i],&y[i]);
scanf("%ld %ld",&ansx,&ansy);
for(int i=n;i>=1;i--)
if((ansx>=a[i])&&(ansx<=a[i]+x[i])&&(ansy>=b[i])&&(ansy<=b[i]+y[i])){
flag=true;
printf("%d\n",i);
break;
}
if(!flag)
printf("-1\n");
fclose(stdin);
fclose(stdout);
return 0;
}1.2hotel
題目簡(jiǎn)述：
求一段有A,B兩種屬性的序列中,滿足Ai=Aj,并且存在Bk（i<=k<=j）<=W的無(wú)序二元組的組數(shù).
分析1：
這是一個(gè)靜態(tài)統(tǒng)計(jì)問(wèn)題.先不妨設(shè)i<j,防止統(tǒng)計(jì)時(shí)重復(fù),也能很快的想到按屬性A分開(kāi)處理,我們可以利用動(dòng)態(tài)規(guī)劃的思想來(lái)解決.
實(shí)現(xiàn)1：
T[i]表示第i個(gè)元素前最近的滿足Bk<=W元素的位置；
G[i][j]表示在前j 元素中屬性A為i的元素的個(gè)數(shù).
首先計(jì)算出G[i][j]:
若Aj=i,則G[i][j]=G[i][j-1]+1;
否則G[i][j]=G[i][j-1];
然后一邊計(jì)算T[i],一邊統(tǒng)計(jì)總數(shù)ans：
若i本身滿足Bi<=W則T[i]=i,ans+=G[Ai][T[i]]-1（自己不能和自己成組）；
否T[i]=T[i-1], ans+=G[Ai][T[i]].
最后時(shí)間復(fù)雜度T=O(kn),空間復(fù)雜度S=O(kn) .
分析2：
本題還有不同的思路.如:使用ST算法的O(nlog2n)的算法,和同樣是DP預(yù)處理但構(gòu)造得比較精妙的O(n)的算法。具體實(shí)現(xiàn),以后再寫(xiě).
總結(jié)：
O(kn)的算法很容易想到,但更快的算法比較困難,畢竟我在考場(chǎng)上還想錯(cuò)了.如果題目可以用O(kn)的方法解決,那么在考試時(shí)最好不要想O(n)或O(nlog2n)的算法.
O(kn)
#include<cstdio>
#include<cstring>
#include<iostream>
const long maxn=200001;
const long maxm=51;
int c[maxn];
bool t[maxn];
int G[maxm][maxn];
int T[maxn];
long long ans=0;
int main(){
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
memset(t,false,sizeof(t));
memset(G,0,sizeof(G));
long n,m,p;//n:hotels m:colours
int q;
scanf("%ld %ld %ld",&n,&m,&p);
for(int i=1;i<=n;i++){
scanf("%d %d",&c[i],&q);
if(q<=p)
t[i]=true;
}
for(int j=0;j<=m-1;j++)
for(int i=1;i<=n;i++)
{
if(j==c[i])
G[j][i]=G[j][i-1]+1;
else
G[j][i]=G[j][i-1];
}
for(int i=1;i<=n;i++){
if(t[i]){
T[i]=i;
ans+=(long long)G[c[i]][T[i]]-1;
}
else{
T[i]=T[i-1];
ans+=(long long)G[c[i]][T[i]];
}
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
1.3mayan
題目簡(jiǎn)述：
有一個(gè)游戲,通過(guò)交換左右兩個(gè)方塊,使三個(gè)或三個(gè)以上的同色方塊連成一線而消除掉,當(dāng)下方方塊消除后,上面的方塊會(huì)掉落.求在規(guī)定步數(shù)時(shí),方塊剛好全部消除的字典序最小方案.
分析：
搜索.
實(shí)現(xiàn)：
這道題很復(fù)雜,編寫(xiě)的內(nèi)容非常的多,由于我水平不高,只是寫(xiě)了在一層中平移互換的部分.
總結(jié)：
要多練習(xí)搜索題.
30%
#include<cstdio>
#include<cstring>
#include<iostream>
int flag=true;
int tot;
int ansx[5],ansy[5],ansc[5];
void work(int i,int p[5]);
int main(){
freopen("mayan.in","r",stdin);
freopen("mayan.out","w",stdout);
int p[5];
memset(p,0,sizeof(p));
int t;
scanf("%d",&tot);
for(int i=0;i<=4;i++)
for(int j=1;;j++)
{
if(j>2){
flag=false;
break;
}
scanf("%d ",&t);
if(t)
p[i]=t;
else
break;
}
if(flag)
work(0,p);
else
printf("-1");
if(flag)
printf("-1");
fclose(stdin);
fclose(stdout);
return 0;
}
void work(int i,int p[5]){
int q[5];
if(!flag)
return ;
if(i==tot){
if((!p[1])&&(!p[2])&&(!p[3])&&(!p[4])&&(!p[0]))
{
for(int j=0;j<=tot-1;j++)
printf("%d %d %d\n",ansx[j],ansy[j],ansc[j]);
flag=false;
return;
}
return;
}
for(int x=0;x<=4;x++)if(p[x]){
for(int a=0;a<=4;a++)
q[a]=p[a];
if(x<4&&q[x]){
q[x]^=q[x+1];q[x+1]^=q[x];q[x]^=q[x+1];
for(int a=0;a<=2;a++){
int t=q[a],b;
for(b=a+1;b<=4;b++)
if(q[b]-t)
break;
if(b-a>=3)
for(b=a;b<=4;b++)
if(q[b]==t)
q[b]=0;
}
ansx[i]=x;
ansy[i]=0;
ansc[i]=1;
work(i+1,q);
}
for(int a=0;a<=4;a++)
q[a]=p[a];
if(x>0&&q[x]){
q[x]^=q[x-1];q[x-1]^=q[x];q[x]^=q[x-1];
for(int a=0;a<=2;a++){
int t=q[a],b;
for(b=a+1;b<=4;b++)
if(q[b]-t)
break;
if(b-a>=3)
for(b=a;b<=4;b++)
if(q[b]==t)
q[b]=0;
}
ansx[i]=x;
ansy[i]=0;
ansc[i]=-1;
work(i+1,q);
}
}
}
Day2：
2.1factor
題目簡(jiǎn)述：
求(ax+by)n中xnym項(xiàng)的次數(shù).
分析：
利用二項(xiàng)式展開(kāi)定理,系數(shù)為C(n,n+m) anbm
實(shí)現(xiàn)：
遞推求出組合數(shù)C[i][j]=C[i-1][j-1]+C[i-1][j],一邊加一邊取模.再一邊乘一邊取模,乘上anbm即可.
T=O((n+m)2),S=O((n+m)2).
總結(jié)：
取模的運(yùn)算遵循乘法和加法的結(jié)合律,但不支持除法.如果要用公式法算組合數(shù),需要先分解質(zhì)因數(shù),
約分后再乘才行.相比之下使用遞推法算組合數(shù)就更好一些
代碼
#include<cstdio>
#include<cstring>
#include<iostream>
long c[1001][1001];
int main(){
freopen("factor.in","r",stdin);
freopen("factor.out","w",stdout);
long a,b,n,m,k;
long const mod=10007;
long ans=1;
memset(c,0,sizeof(c));
scanf("%ld %ld %ld %ld %ld",&a,&b,&k,&n,&m);
a%=mod;
b%=mod;
for(int i=1;i<=k;i++)
c[i][0]=c[i][i]=1;
for(int i=2;i<=k;i++)
for(int j=1;j<=i-1;j++){
c[i][j]=c[i-1][j]+c[i-1][j-1];
if(c[i][j]>mod)
c[i][j]-=mod;
}
ans*=c[k][n];
if(ans>mod)
ans-=mod;
for(int i=1;i<=n;i++){
ans*=a;
ans%=mod;
}
for(int i=1;i<=m;i++){
ans*=b;
ans%=mod;
}
printf("%ld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
2.2
題目簡(jiǎn)述：
給定n個(gè)含有w, v兩種屬性的元素和m個(gè)區(qū)間,選一個(gè)W,使公式：
Yi=∑1*∑vj,j∈[Li,Ri]且wj≥W
計(jì)算出的∑Yi與給定的值Y之間的差的絕對(duì)值最小。
分析:
這是一道動(dòng)態(tài)統(tǒng)計(jì)的問(wèn)題,但仔細(xì)分析,∑Yi隨W增大而單調(diào)不增,所以我們可以先二分答案,讓后把它改為靜態(tài)的統(tǒng)計(jì)問(wèn)題.對(duì)于多區(qū)間的統(tǒng)計(jì),有不同的解決方法,所以同樣使用二分答案,本題的得分也在50～100之間.
實(shí)現(xiàn)1：
單獨(dú)處理每個(gè)區(qū)間,按照公式計(jì)算即可.
T=O(n2log2maxw),S=O(n).
實(shí)現(xiàn)2：
使用線段樹(shù).這是一個(gè)錯(cuò)誤的想法,是在錯(cuò)誤預(yù)估 O(nlog2nlog2maxw)的時(shí)間可以通過(guò)的前提下做出的選擇,其實(shí)一開(kāi)使想到O(n)的掃描線算法(其實(shí)這已經(jīng)是一個(gè)錯(cuò)誤的想法了,因?yàn)閽呙杈€是用于對(duì)于多區(qū)間覆蓋,無(wú)關(guān)聯(lián)的點(diǎn)的簡(jiǎn)單統(tǒng)計(jì)用的,而對(duì)于有重疊的區(qū)間統(tǒng)計(jì)和較復(fù)雜的公式就無(wú)能為了力了),也聯(lián)想到樹(shù)狀數(shù)組,覺(jué)得功能不足以完成較復(fù)雜的公式計(jì)算.其實(shí)沒(méi)有想到正確的統(tǒng)計(jì)方法,要不然不僅是樹(shù)狀數(shù)組,連什么數(shù)據(jù)結(jié)構(gòu)都不用也可以解決.
具體實(shí)現(xiàn)方式就是每次插入m條線段,并遞歸同時(shí)計(jì)算出∑1和∑vj,最后求和計(jì)算.
T=O(nlog2nlog2maxw),S=O(n).
實(shí)現(xiàn)3：
其實(shí)類(lèi)似的統(tǒng)計(jì)題是做過(guò)的,但看到復(fù)雜的公式就沒(méi)有想到改進(jìn).我們可以用動(dòng)態(tài)規(guī)劃的思想來(lái)解決這個(gè)問(wèn)題：用t[i]表示前i個(gè)元素中符合條件的元素的個(gè)數(shù),用sum[i]表示前i個(gè)元素中符合條件元素的v的值的和,那么對(duì)于區(qū)間[l,r],最后的值就是(sum[r]-sum[l-1])*(t[r]-t[l-1]).我們預(yù)處理出t[i]和sum[i]的值,然后對(duì)每個(gè)區(qū)間操作一次即可。
T=O((n+m)log2maxw),S=O(n).
總結(jié)：
好多人沒(méi)有得滿分的原因是二分查找沒(méi)有注意邊界,但也有像我一樣腦殘的人想到了高級(jí)的線段樹(shù),而忽視了簡(jiǎn)單的預(yù)處理,還浪費(fèi)了不少的時(shí)間。
線段樹(shù)悲劇
#include<cstdio>
#include<cstring>
#include<iostream>
long n,m;
long long S;
long long T;
long w[200001],v[200001];
long r[200001],l[200001];
long A[800001],B[800001];
long X[800001],P[800001];
long xx,pp;
long Hash[200001];//=Hash(x);
long Hass[200001];//=Hash-1(x);
long tHash=0;
long root;
long W;
long maxw=0;
long long work(long q);
void build(long i,long a,long b);
void count(long i,long a,long b);
void recount(long i,long a,long b);
inline long long abs(long long a,long long b){return (a-b>0)?(a-b):(b-a);}
int main(){
freopen("qc.in","r",stdin);
freopen("qc.out","w",stdout);
memset(Hash,0,sizeof(Hash));
long low,high,t;
long long g,k;
scanf("%ld %ld %lld",&n,&m,&S);
for(long i=1;i<=n;i++){
scanf("%ld %ld",&w[i],&v[i]);
if(w[i]>maxw)
maxw=w[i];
}
for(long i=1;i<=m;i++){
scanf("%ld %ld",&l[i],&r[i]);
Hash[l[i]]=Hash[r[i]]=1;
}
for(long i=1;i<=n;i++)
if(Hash[i]){
tHash++;
Hass[tHash]=i;
Hash[i]=tHash;
}
build(1,1,tHash);
low=0;high=maxw;
//g=work(4);printf("%lld",g);return 0;
g=work(high);
if(g>S){
printf("%lld",g-S);
fclose(stdin);
fclose(stdout);
return 0;
}
g=work(low);
if(g<S){
printf("%lld",S-g);
fclose(stdin);
fclose(stdout);
return 0;
}
while(low<=high){
t=(low+high)/2;
if(low+1==high)
break;
g=work(t);
if(g-S>0)
low=t;
else
high=t;
}
g=work(low);
g=abs(g,S);
k=work(high);
k=abs(k,S);
if(g<k)
printf("%lld",g);
else
printf("%lld",k);
fclose(stdin);
fclose(stdout);
return 0;
}
void build(long i,long a,long b){
A[i]=a;B[i]=b;
if(a+1!=b){
build(i*2,a,(a+b)/2);
build(i*2+1,(a+b)/2,b);
}
}
void count(long i,long a,long b){//
X[i]=P[i]=0;
if(a+1==b){
for(int k=Hass[a];k<=Hass[b];k++)
if(w[k]>=W){
X[i]++;
P[i]+=v[k];
}
}
else{
count(i*2,a,(a+b)/2);
count(i*2+1,(a+b)/2,b);
X[i]=X[i*2]+X[i*2+1];
P[i]=P[i*2]+P[i*2+1];
if(w[Hass[(a+b)/2]]>=W){
X[i]--;
P[i]-=v[Hass[(a+b)/2]];
}
}
return ;
}
void recount(long i,long a,long b){
if(A[i]==a&&B[i]==b){
xx+=X[i];
pp+=P[i];
return;
}
else if(b<=(A[i]+B[i])/2)
recount(i*2,a,b);
else if((a>=(A[i]+B[i])/2))
recount(i*2+1,a,b);
else {
recount(i*2,a,(A[i]+B[i])/2);
recount(i*2+1,(A[i]+B[i])/2,b);
if(w[Hass[(A[i]+B[i])/2]]>=W){
xx--;
pp-=v[Hass[(A[i]+B[i])/2]];
}
}
}
long long work(long q){
W=q;
T=0;
count(1,1,tHash);
for(long i=1;i<=m;i++){
xx=pp=0;
if(l[i]!=r[i])
recount(1,Hash[l[i]],Hash[r[i]]);
else if(w[l[i]]>W)
T+=(long long)w[l[i]]*v[l[i]];
T+=(long long)xx*pp;
}
return T;
}
AC代碼
#include<cstdio>
#include<cstring>
#include<iostream>
long n,m;
long long S;
long w[200001],v[200001];
long r[200001],l[200001];
long long sum[200001];
long t[200001];
long xx,pp;
long root;
long maxw=0;
long long work(long q);
inline long long abs(long long a,long long b){return (a-b>0)?(a-b):(b-a);}
int main(){
freopen("qc.in","r",stdin);
freopen("qc.out","w",stdout);
long low,high,t;
long long g,k;
scanf("%ld %ld %lld",&n,&m,&S);
for(long i=1;i<=n;i++){
scanf("%ld %ld",&w[i],&v[i]);
if(w[i]>maxw)
maxw=w[i];
}
for(long i=1;i<=m;i++){
scanf("%ld %ld",&l[i],&r[i]);
}
low=0;high=maxw;
g=work(high);
if(g>S){
printf("%lld",g-S);
fclose(stdin);
fclose(stdout);
return 0;
}
g=work(low);
if(g<S){
printf("%lld",S-g);
fclose(stdin);
fclose(stdout);
return 0;
}
while(low<=high){
t=(low+high)/2;
if(low+1==high)
break;
g=work(t);
if(g-S>0)
low=t;
else
high=t;
}
g=work(low);
g=abs(g,S);
k=work(high);
k=abs(k,S);
if(g<k)
printf("%lld",g);
else
printf("%lld",k);
fclose(stdin);
fclose(stdout);
return 0;
}
long long work(long q){
long W=q;
long long T=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1];
t[i]=t[i-1];
if(w[i]>W){
t[i]++;
sum[i]+=v[i];
}
}
for(int i=1;i<=m;i++)
T+=(sum[r[i]]-sum[l[i]-1])*(t[r[i]]-t[l[i]-1]);
return T;
} 2.3bus
題目簡(jiǎn)述：
有序的n個(gè)點(diǎn)組成一個(gè)序列,有m個(gè)單位在時(shí)間Ti出現(xiàn)在其中的一點(diǎn)Ai要移動(dòng)到比Ai大的一點(diǎn)Bi,只有所有要到Ai點(diǎn)以后的單位都到了Ai點(diǎn),才可以出發(fā)到下一個(gè)點(diǎn),每?jī)蓚€(gè)相鄰的點(diǎn)之間有一定權(quán)值的距離.可以通過(guò)k次調(diào)整,每次使相鄰點(diǎn)之間的距離-1,可以重復(fù)調(diào)整.求所有點(diǎn)移動(dòng)的最小時(shí)間和.
分析1：
題目不是很好懂,大略讀懂題目后,觀察數(shù)據(jù)中有k<=1的30%的數(shù)據(jù),于是枚舉即可.
實(shí)現(xiàn)1：
d[i]表示第i個(gè)點(diǎn)到第i+1個(gè)點(diǎn)的權(quán)值,a[i],b[i],t[i]如題目簡(jiǎn)述所示.latest[i]表示到第i個(gè)點(diǎn)的元素最晚的到達(dá)值,arrive[i]表示集體到第i個(gè)點(diǎn)的時(shí)間.當(dāng)k=0時(shí):
arrive[i]=max(arrive[i-1],latest[i-1])+d[i-1],
ans=∑(arrive[b[i]]-t[i])
當(dāng)k=1時(shí),枚舉出一個(gè)d[i],減去1,計(jì)算出最優(yōu)的ans即可.T=O(n2),S=O(n).
分析2：
我們考慮怎樣使用調(diào)整.顯然對(duì)于latest[i]>=arrive[i],對(duì)于i點(diǎn)以后的單位所需的時(shí)間沒(méi)有任何影響,感覺(jué)這里的許多操作應(yīng)該是獨(dú)立的,大概可以用貪心的方法來(lái)解題,然而需要一個(gè)衡量標(biāo)準(zhǔn),這正是在考場(chǎng)上沒(méi)想到的.
實(shí)現(xiàn)2：
用next[i]表示在第i個(gè)點(diǎn)后離i最近的滿足latest[i]>=arrive[i]的點(diǎn),sum[i]表示前i個(gè)點(diǎn)的單位數(shù).
我們可以用sum[next[i]]-sum[i]來(lái)衡量在第i-1到第i個(gè)點(diǎn)之間調(diào)整的效果,每次選擇該值最大的邊,把d的值-1,然后重新計(jì)算arrive[i]的值,再做相同操作.此時(shí)時(shí)間復(fù)雜度O(kn),還不足以通過(guò)全部的數(shù)據(jù).其實(shí)很簡(jiǎn)單的想一想,如果把d[i]的值-1后仍然有所有滿足latest[i]>=arrive[i]的點(diǎn)的狀態(tài)不會(huì)改變并且d[i]仍然可以-1,那么下次調(diào)整的還是i-1到i的這條邊.我們不妨一次性把它做到位,讓d[i]減去一個(gè)恰好的數(shù)(我是拿KM算法的松弛量類(lèi)比的)最終T=O(n2),S=O(n).
總結(jié)：
本來(lái)想在后面70%中隨便貪心做做的,但時(shí)間不夠了,當(dāng)時(shí)想的貪心法已經(jīng)很接近這個(gè)解法了,如果第二題能節(jié)約更多的時(shí)間的話,就可以給這題留出更大的希望.
果斷30%
#include<cstdio>
#include<cstring>
#include<iostream>
long n,m,k;
long d[10001];
long t[10001],a[10001],b[10001];
long latest[10001];
long arrive[10001];
long ans=0;
long qqq;
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
memset(latest,0,sizeof(latest));
scanf("%ld %ld %ld",&n,&m,&k);
for(int i=1;i<=n-1;i++)
scanf("%ld",&d[i]);
for(int i=1;i<=m;i++){
scanf("%ld %ld %ld",&t[i],&a[i],&b[i]);
if(t[i]>latest[a[i]])
latest[a[i]]=t[i];
}
if(k==0){
int tt=latest[1];
for(int i=2;i<=n;i++){
arrive[i]=tt+d[i-1];
tt=arrive[i];
if(latest[i]>tt)
tt=latest[i];
}
for(int i=1;i<=m;i++)
ans+=arrive[b[i]]-t[i];
printf("%ld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
if(k==1){
qqq=100000000;
for(int j=1;j<=n-1;j++){
ans=0;
d[j]--;
memset(arrive,0,sizeof(arrive));
int tt=latest[1];
for(int i=2;i<=n;i++){
arrive[i]=tt+d[i-1];
tt=arrive[i];
if(latest[i]>tt)
tt=latest[i];
}
for(int i=1;i<=m;i++)
ans+=arrive[b[i]]-t[i];
if(ans<qqq)
qqq=ans;
d[j]++;
}
printf("%ld",qqq);
fclose(stdin);
fclose(stdout);
return 0;
}
fclose(stdin);
fclose(stdout);
return 0;
}
其實(shí)AC也不難
#include<cstdio>
#include<cstring>
#include<iostream>
long n,m,k;
long d[10001];
long t[10001],a[10001],b[10001];
long latest[10001];
long arrive[10001];
long sum[10001];
long next[10001];
long ans=0;
long qqq;
long dd;
long maxl;
long maxint=1000000000;
long inline max(long a,long b){return a>b?a:b;}
long inline min(long a,long b){return a<b?a:b;}
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
memset(latest,0,sizeof(latest));
memset(sum,0,sizeof(sum));
scanf("%ld %ld %ld",&n,&m,&k);
for(int i=1;i<=n-1;i++)
scanf("%ld",&d[i]);
for(int i=1;i<=m;i++){
scanf("%ld %ld %ld",&t[i],&a[i],&b[i]);
if(t[i]>latest[a[i]])
latest[a[i]]=t[i];
sum[b[i]]++;
}
for(int i=1;i<=n;i++)
sum[i]+=sum[i-1];
while(1){
maxl=1;
//計(jì)算arrive[i]
arrive[1]=0;
for(int i=2;i<=n;i++)
arrive[i]=max(arrive[i-1],latest[i-1])+d[i-1];
//計(jì)算next[i]
next[n]=n;
for(int i=n-1;i;i--){
next[i]=next[i+1];
if(arrive[i+1]<=latest[i+1])
next[i]=i+1;
}
//貪心選擇最優(yōu)的一條邊操作，一次操作可以直接使d[i]變?yōu)?
while(!d[maxl]&&maxl<=n-1)
maxl++;
if(maxl==n||k==0)
break;
for(int i=maxl+1;i<=n-1;i++)
if(d[i]&&sum[next[maxl]]-sum[maxl]<sum[next[i]]-sum[i])
maxl=i;
if(sum[next[maxl]]-sum[maxl]==0)
break;
dd=maxint;
for(int i=maxl+1;i<=next[maxl]-1;i++)
dd=min(dd,arrive[i]-latest[i]);
dd=min(dd,k);
dd=min(dd,d[maxl]);
k-=dd;
d[maxl]-=dd;
}
for(int i=1;i<=m;i++)
ans+=arrive[b[i]]-t[i];
printf("%ld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
注：本文用T 表示時(shí)間復(fù)雜度,S表示空間復(fù)雜度.復(fù)雜度只表示數(shù)量級(jí),不考慮常數(shù).
還需思考的問(wèn)題：
1.2的O（nlogn）和O（n）的解法
2.1的數(shù)學(xué)方法優(yōu)化？
1.3怎樣爆搜？