問題
http://community.topcoder.com/stat?c=problem_statement&pm=11060&rd=14245
解き方
２つの木のペアのいずれかの傾きが、最適な傾きになることがわかる。
このうち、切らなくてもよい木が一番少なく、かつ地面より下に木がいかなく、
かつ現在存在する木よりも大きい位置にならないようなものを
すべて調べればよい。
コード
class TimeTravellingGardener {
public: int determineUsage(vector<int> distance, vector<int> h) {
int n=h.size();
int sum[n];
sum[0]=0;
FORE(i,0,n-1)sum[i+1]=sum[i]+distance[i];
int ret=n-1;
FORE(i,0,n)FORE(j,i+1,n){
int cnt=0;
if((sum[n-1]-sum[i])*(h[j]-h[i])<-h[i]*(sum[j]-sum[i]))continue;
if((sum[0]-sum[i])*(h[j]-h[i])<-h[i]*(sum[j]-sum[i]))continue;
int valid=1;
for(int k=0;k<n;k++){
if((sum[k]-sum[i])*(h[j]-h[i])>(h[k]-h[i])*(sum[j]-sum[i])){
valid=0;
break;
}
if((sum[k]-sum[i])*(h[j]-h[i])!=(h[k]-h[i])*(sum[j]-sum[i])){
cnt++;
}
}
if(valid)ret=min(ret,cnt);
}
return ret;
}
};
public: int determineUsage(vector<int> distance, vector<int> h) {
int n=h.size();
int sum[n];
sum[0]=0;
FORE(i,0,n-1)sum[i+1]=sum[i]+distance[i];
int ret=n-1;
FORE(i,0,n)FORE(j,i+1,n){
int cnt=0;
if((sum[n-1]-sum[i])*(h[j]-h[i])<-h[i]*(sum[j]-sum[i]))continue;
if((sum[0]-sum[i])*(h[j]-h[i])<-h[i]*(sum[j]-sum[i]))continue;
int valid=1;
for(int k=0;k<n;k++){
if((sum[k]-sum[i])*(h[j]-h[i])>(h[k]-h[i])*(sum[j]-sum[i])){
valid=0;
break;
}
if((sum[k]-sum[i])*(h[j]-h[i])!=(h[k]-h[i])*(sum[j]-sum[i])){
cnt++;
}
}
if(valid)ret=min(ret,cnt);
}
return ret;
}
};
Share this
Related Posts
SRM 542 DIV1 Easy - PatrolRoute
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11934&rd=14734
解き方
３点を選んだ時、そのｘ座標の最小値と最大値の- SRM 590 DIV1 Easy - FoxAndChess
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12725&rd=15702
解き方
左にある要素から順に、
①アルファベットが一
- SRM 670 DIV1 Easy - DoubleOrOneEasy
問題
https://community.topcoder.com/stat?c=problem_statement&pm=14059&rd=16550
解き方
文字列長がnのとき、条件を満たすLCSは必
- SRM 491 DIV1 Easy - FoxMakingDice
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11234&rd=14244
解き方
Kを固定することで、そのKを作ることのできる組