アリスは幼稚園の先生です。彼女はクラスの子供たちにキャンディーをあげたいと思っています。すべての子供たちが一列に並んで座り、それぞれの通常のパフォーマンスに応じて評価スコアが付けられます。アリスは、各子供に少なくとも 1 つのキャンディーを与えたいと考えています。子供はなんとなく嫉妬しているからです。一方の評価が他方よりも高い場合、アリスは、隣接する 2 人の子供の評価対象に従って、キャンディーを与えなければなりません。アリスはお金を節約したいので、キャンディーの合計をできるだけ少なくしたいと考えています。
入力の最初の行は整数Nで、アリスのクラスの子供の数です。次の各行にNは、各子供の評価を示す整数が含まれています。
出力の唯一の行に、アリスが与えなければならないキャンディーの最小数を表す整数が表示されます。
3
1
2
2
4
アリスがあげなければならないキャンディーの数は、1、2、1 です。
N各子供の評価は 10^5 以下です。
誰でも私を助けてもらえますか？
これは 2 つのパスで行うことができます。全員がキャンディーを1つ持つことから始めます。
最初のループ i から 1 から n-1 (ゼロベース)、評価[i] > 評価[i-1] の場合、candies[i] = candies[i-1]+1
次に、i を n-2 から 0 までループします。評価[i] > 評価[i+1]の場合、キャンディー[i] = max(キャンディー[i]、キャンディー[i+1]+1)
2 番目のループは 1 番目のループで修正されたものを壊すことはできず、考えられるすべての評価の不一致は 2 つのループのいずれかでキャッチする必要があるため、これによりキャンディーの有効な分布が得られることを示すのは非常に簡単です。これが最小数のキャンディーを使用するかどうかは明らかではありませんが、各割り当てを詳しく調べると、各ステップで (特定の個人が) 必要とするキャンディーの数の下限を条件が証明していることを示すことができます。
このアルゴリズムの分析をより面白くするために、次の入力を行います。
9
2
3
4
4
4
2
1
3
4
まず、子供がキャンディーを手に入れている子供の隣に座っていてx、その子供が低い評価を持っている場合、最初の子供は少なくともx+1キャンディーを手に入れる必要があることに注意してください。違いを1以上にすると、キャンディーが無駄になります。差は1より大きい必要がある場合もありますが、後でそれが発生したときに説明します。
さて、キャンディーを1つだけ手に入れるべき子供たちを見つけましょう。私は、評価を山脈として視覚化し（評価が大きいほど、その時点で山が高くなります）、1つのキャンディーを取得する必要がある子供を見つけることは、山の谷（両方の隣人がより高い評価または同じ評価を持つポイント）を見つけることとして視覚化します。範囲。与えられた例は次のようになります（谷は矢印で示されています）：
*** *
**** **
****** **
*********
^ ^ ^
このプロセスの目的のために、この線の開始前と終了後に「無限」の高さの2つのピークがあると仮定します。（私が無限と言うときは、入力で可能な値よりも大きいことを意味するので10^5+1、「無限」に使用できます。実際には、問題設定者が入力データにバグを持っている場合に備えて、それよりも大きい値を使用します。）
次のコードを使用して、谷を簡単に見つけることができます。
ratings = ...
N = ...
valleys = []
def get_rating(i):
if i < 0 or i > N-1:
return INFINITY
return ratings[i]
for i from 0 to N-1:
if get_rating(i) <= get_rating(i-1) and get_rating(i) <= get_rating(i+1):
valleys.append(i)
配列valleysには谷のインデックスが含まれています。私たちは、谷を代表する各子供が1つのキャンディーを手に入れるべきであることを知っています。説明のために、谷がインデックス4にあると仮定します。これで、インデックス3と5の子供は少なくとも2つのキャンディーを入手する必要があることがわかりました。インデックス2の子供がインデックス3の子供よりも高い評価を持っている場合、その子供は少なくとも3つのキャンディーを手に入れる必要があります。2以下の場合も同様です。同様に6以上の場合。
私が「少なくとも」と言っていることに注意してください。これはピークが原因です（評価が隣人の両方よりも高い子供、谷とは異なり、この定義に平等を含めないことに注意してください）。ピークには2つの最小制約があり、2つのうち大きい方を選択するだけです。
これで、次のコードを使用して、各子供が手に入れるべきキャンディーの数を見つけることができます。
candies = [0] * N # An array of N 0s
for valley_idx in valleys:
candies[valley_idx] = 1
cur_idx = valley_idx-1
cur_candies = 2
while cur_idx >= 0 and ratings[cur_idx] > ratings[cur_idx+1]:
candies[cur_idx] = max(candies[cur_idx], cur_candies)
cur_idx -= 1
cur_candies += 1
cur_idx = valley_idx+1
cur_candies = 2
while cur_idx < N and ratings[cur_idx] > ratings[cur_idx-1]:
candies[cur_idx] = max(candies[cur_idx], cur_candies)
cur_idx += 1
cur_candies += 1
candies次に、教師が購入する必要のあるキャンディーの数は、配列内の値の合計です。
これを行うと、答えは18サンプル入力またはグラフの形式であることがわかります。
* * *
** ** **
*********
上記の解決策では、同じ評価の隣接する子供は、他の子供との関係で取得するキャンディーの量に制限を設けないと仮定しました。代わりに、両方の子供が同じ量のキャンディーを入手する必要がある場合は、これを考慮してアルゴリズムを非常に簡単に変更できます。
基本的な考え方は、ある種のランレングスエンコーディングを行うことです。これは、同じ評価の子供が1人以上連続しているかどうかに関係なく、隣人が取得するキャンディーの量が変わらないことに気付くためです。5人の子供が5人のキャンディーを手に入れるということは、5人だけでなく、25人のキャンディーを配らなければならないことを意味するので、私たちは連続した子供の数を追跡する必要がありますmultipliers。次のコードを使用して、新しいratings配列と配列を見つけますmultipliers。
new_ratings = [ratings[0]]
multipliers = [1]
for i from 1 to N-1:
if ratings[i] == new_ratings[len(new_ratings)-1]:
multipliers[len(new_ratings)-1] += 1
else:
new_ratings.append(ratings[i])
multipliers.append(1)
ここで、配列に対して元のアルゴリズムを実行し、new_ratings配列を取得しcandiesます。次に、実際に実行できるキャンディーの量を取得します。
answer = 0
for i from 0 to len(new_ratings)-1:
answer += multipliers[i] * candies[i]
これを行うと、答えは20サンプル入力またはグラフの形式であることがわかります。
*** *
***** **
*********
この問題を解決するために、単純な DP アプローチを使用しました。評価が以前のものよりも大きい場合は、DP テーブルの i 番目の値を増やします。そうでない場合は、2 つの条件が存在する可能性があります。1 つの条件は、前のインデックスの DP 値が 1 であり、次の値よりも小さい値を取得し、DP を更新し続けるまで逆の順序でトラバースすることです。もう 1 つの条件は、前のインデックスの DP 値が 1 より大きい場合です。この場合、DP の現在のインデックスには 1 が割り当てられます。
for(int i=1; i <= n; i++){
scanf("%d", ra+i);
if( ra[i] > ra[i-1] )
dp[i] = dp[i-1] + 1;
else if( dp[i-1] == 1 ){
dp[i] = 1;
for( int j=i-1; j>0; j-- )
if( ra[j] > ra[j+1] )
dp[j] = max ( dp[j+1] + 1, dp[j] );
else
break;
}
else
dp[i] = 1;
}
long long sum = 0;
for(int i = 1;i <= n; i++)sum+= dp[i];
printf("%lld\n",sum);
私たちが持っているとしましょう
1, 5, 2, 10, 10 3, 8, 9 , 1 , 1, 2 は、S1 から S11 までの 11 人の学生の評価として
評価が y 軸にプロットされているグラフの評価と学生を作成するとします。
ローカル ミニマムは常に 1 つのキャンディーを取得するため、学生 S1 、S3、S6、S9 および S10 はローカル ミニマムになり、1 つのキャンディーを取得します。私たちが言うことから逸脱する最小解 (So) があると主張することができます。次に、すべての生徒が同じキャンディーを取得し、逸脱する極小値が 1 つのキャンディーを取得するもう 1 つの解 (So1) を作成できます。その場合、So1 は次のようになります。最小であるため、極小値が 1 を超えるキャンディーを取得する最小解は存在しません。
極小値を取得したら、極小値の左右を横断して、他の学生のキャンディーを計算できます。
極大値の場合、隣接するノード +1 の値より大きくなります。作業コードは以下のとおりです。時間の複雑さは O(n) で、空間の複雑さは O(n) です。
public static int candy(ArrayList<Integer> a) {
int size = a.size();
int[] cand = new int[size];
// give all children candies equal to 1
// local minimas will get 1
for(int i = 0; i < size; i++)
{
cand[i] = 1;
}
// increase count on the right of local minimas
for(int i = 1; i < size; i++)
{
if(a.get(i) > a.get(i-1))
{
cand[i] = cand[i-1]+1;
}
}
// increase count on the left of local minimas
// local maximas should be max of left and right
for(int i = size-2; i >= 0; i--)
{
if(a.get(i) > a.get(i+1))
{
cand[i] = Math.max(cand[i], cand[i+1]+1);
}
}
// get the sum
int count = 0;
for(int i = 0; i < size; i++)
{
count = count + cand[i];
}
return count;
}
HackerEarth Problem でテスト ケースを使用してテストできます: https://www.hackerrank.com/challenges/candies
リートコード : https://leetcode.com/problems/candy/
これが機能する理由の詳細な説明は、@ http://stackandqueue.com/?p=108で見つけることができます。
これが可能な解決策の1つである可能性があると感じました...
def candy(N,r):
H=[0]*N
R=r
cur_can=1
cand=[0]*N
cand[0]=1
#print R#,'\n',cand
for i in range(0,N):
if i!=0:
#print R[i],' ',R[i-1]
if R[i]>R[i-1]:
cand[i]=cand[i-1]+1
else:
cand[i]=1
## print R[i],i
sum=0
## print i
print cand
for j in range(0,N):
sum+=cand[j]
return sum
r=[1,2,2,4,1,2,4]
N=len(r)
print candy(N,r)
コードでサンプルとして使用される値の出力は、答えとして 12 を与えます。これは私には正しいように思えます...どう思いますか?
これはさほど難しい問題ではないと思います。よく考えてみれば、自分なりの答えが得られるでしょう。
#include <iostream>
#include <queue>
using namespace std;
#define CALC(n) (n)+(n)*((n)-1)/2
struct PAIR {
int n;int up;//up=0,1,2; 0是升，1是平，2是降
public:
PAIR(int _n,int _u){
n=_n;up=_u;
}
};
int N;
queue<PAIR> q;
int calc(int up,int p){
if(up==1)
return p;
else {
return p+p*(p-1)/2;
}
}
int getType(int lc,int c){
int up=-1;
if(c>lc)
up=0;
else if(c==lc)
up=1;
else
up=2;
return up;
}
int main(int argc, const char * argv[])
{
scanf("%d",&N);
int lastChild,child,n=2;
long long result=0;
scanf("%d%d",&lastChild,&child);N-=2;
int up=getType(lastChild, child);
lastChild=child;
while (N--) {
scanf("%d",&child);
int tu=getType(lastChild, child);
if(tu==up)
n++;
else {
q.push(PAIR(n,up));
n=2;
up=tu;
}
lastChild=child;
}
q.push(PAIR(n,up));
q.push(PAIR(1,1));
/*其实主要就是看转折点是属于上一段还是当前段。
如果是正V的话，转折点属于后一段。前一段的和-1.
如果是倒V的话，转折点属于长的一段。
然后是平的和别的有搭配的话，转折点属于别的
*/
PAIR lastp=q.front();q.pop();
while(q.size()){
PAIR pir=q.front();q.pop();
if(pir.up==1){
result+=calc(lastp.up,lastp.n);//如果下一段是平的，就把转折点分到上一段
pir.n-=1;
}
else if(lastp.up==1){
result+=calc(lastp.up,lastp.n-1);//如果上一段是平的，就把转折点分到下一段
} else if((lastp.up==0)&&(pir.up==2)){//如果是倒V型的，转折点属于长的
if(lastp.n>pir.n){
result+=calc(lastp.up,lastp.n);
pir.n-=1;
} else {
result+=calc(lastp.up,lastp.n-1);
}
} else if((lastp.up==2)&&(pir.up==0)){//如果是正V型的，转折点属于后一个
result+=calc(lastp.up,lastp.n)-1;
} else {
printf("WRONG!");
}
lastp=pir;
}
printf("%lld\n",result);
return 0;
}
2 つのキューを使用して、割り当てられていないインデックスの増加シーケンスと減少シーケンスを保存し、隣接する評価のすべての可能な状況を列挙し、評価が横ばいまたは底に達したとき (つまり、現在の評価がローカル最小値または以前と同じとき) にキャンディーを割り当てました。
これが私の解決策です：
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <deque>
void assigncandies(std::deque<int>& incr, std::deque<int>& decr, unsigned int& total) {
int incrlen = incr.size();
int decrlen = decr.size();
if (incrlen >= decrlen) {
int num=incrlen;
int last = incr.back();
while(!incr.empty()) {
int idx = incr.back();
total += num;
incr.pop_back();
num --;
}
if (!decr.empty()) {
if (last == decr.front()) decr.pop_front();
num=1;
while(!decr.empty()) {
int idx = decr.back();
//candies[idx]=num;
total += num;
decr.pop_back();
num ++;
}
}
} else {
int num=decrlen;
int last = decr.front();
while (!decr.empty()) {
int idx = decr.front();
//candies[idx]=num;
total += num;
decr.pop_front();
num --;
}
if (!incr.empty()) {
if (last == incr.back()) incr.pop_back();
num=1;
while(!incr.empty()) {
int idx = incr.front();
//candies[idx]=num;
total += num;
incr.pop_front();
num ++;
}
}
}
}
int main () {
int N;
unsigned int total=0;
int PrevR, CurR, NextR;
std::cin >> N;
std::deque<int> incr;
std::deque<int> decr;
for (int i = 0; i<N;i++) {
if (i==0) {
std::cin>>CurR;
std::cin >> NextR;
} else if (i != N-1) std::cin >> NextR;
if (i==0) {
if (CurR>NextR) decr.push_back(0);
else if (CurR<NextR) incr.push_back(0);
else total=1;
} else if (i==N-1) {
if (PrevR<CurR) {
incr.push_back(i);
}
if (PrevR>CurR) {
decr.push_back(i);
}
if (PrevR==CurR) {
total += 1;
}
assigncandies(incr,decr,total);
} else {
if (PrevR == CurR && CurR == NextR) {
assigncandies(incr,decr,total);
total += 1;
}
if (PrevR == CurR && CurR < NextR) {
assigncandies(incr,decr,total);
incr.push_back(i);
}
if (PrevR == CurR && CurR > NextR) {
assigncandies(incr,decr,total);
decr.push_back(i);
}
if (PrevR < CurR) {
incr.push_back(i);
if (CurR > NextR) decr.push_back(i);
}
if (PrevR > CurR && CurR >= NextR) {
decr.push_back(i);
}
if (PrevR > CurR && CurR < NextR) {
decr.push_back(i);
assigncandies(incr,decr,total);
total -= 1;
incr.push_back(i);
}
}
PrevR = CurR;
CurR = NextR;
}
std::cout<<total<<std::endl;
return 0;
}
テストケースに合格し、3/10 ケースは正しいですが、残りの部分でセグメンテーション違反が発生しました。
誰かが私のコードの何が問題なのかを指摘できるかどうか疑問に思っています。
どうもありがとうございました！
おそらく最も簡単な解決策：
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int children;
int sum=0;
cin >> children;
int ratings[children];
int candies[children];
//give all children 1 candy to start
for(int i=0;i<children;++i)
{
cin >> ratings[i];
candies[i] = 1;
}
//if the current child has a better rating than the child
//before him he is entitled to +1 greater candy than that child
for(int i=1;i<children;++i)
{
if(ratings[i] > ratings[i-1])
candies[i] = candies[i-1]+1;
}
// work backwards to break any discrepancies ex.
// rating[5,4,3] -> candies[1,1,1] -> candies [1,1,1] -> candies [3,2,1]
// starting ratings give everyone 1 first loop second loop
for(int i=children-1;i>=0;--i)
{
if(ratings[i] > ratings[i+1])
{
candies[i] = max(candies[i],candies[i+1]+1);
}
}
for(int i=0;i<children;++i)
{
sum+=candies[i];
}
cout << sum;
return 0;
}
# this python code solves the problem for all test cases on interviewstreet
#!/usr/bin/python
if __name__ == "__main__":
N = int(raw_input().strip())
scores = []
for i in range(N):
scores.append(int(raw_input().strip()))
nc = []
if(scores[0]>scores[1]):
nc.append(-1)
else:
nc.append(0)
for i in range(1,N-1):
if (scores[i] > scores[i-1]) and (scores[i]>scores[i+1]):
nc.append(2)
elif (scores[i] > scores[i-1]):
nc.append(1)
elif (scores[i]>scores[i+1]):
nc.append(-1)
else:
nc.append(0)
if(scores[N-1]> scores[N-2]):
nc.append(1)
else:
nc.append(0)
noc = []
for i in range(N):
noc.append(0)
for i in range(N):
if(nc[i]==0):
noc[i] = 1
for i in range(N):
if(nc[i]==1) and (noc[i-1]!=0):
noc[i] = noc[i-1]+1
for i in range(N-1,-1,-1):
if(nc[i]==-1) and (noc[i+1]!=0):
noc[i] = noc[i+1]+1
for i in range(N):
if(nc[i]==2) and (noc[i-1]!=0) and (noc[i+1]!=0):
noc[i] = max((noc[i-1],noc[i+1]))+1
nt = sum(noc)
print nt
要約する：
#include <vector>
#include <iostream>
using namespace std;
int main() {
int N;
cin>>N;
vector<int> A(N,0),B(N,1);
for(int i=0;i<N;++i) cin>>A[i];
for(int i=0;i<N;++i) if(A[i]>A[i-1]) B[i]=B[i-1]+1;
for(int j=N-2;j>=0;--j) if (A[j]>A[j+1]) B[j] = max(B[j], B[j+1]+1);
int sum=0;
for(int i=0;i<N;++i) sum+=B[i];
cout<<sum<<endl;
return 0;
}
AS mentioned by others,scanning left to right and then right to left,and getting max candies used at certain postion is working.
Before this, i used other way,which seemed to be working and i checked it with many different inputs,although i couldnt clearly write it in code,Here is the Algo:
Algorithm:
1.Use an int[]index array and store all the indexes in the sorted value of thie ranks.
so here
int values[]=9 2 3 6 5 4 3 2 2 2
so index sorted array would be
int index[]= 1 7 8 9 2 6 5 4 3 0
now int[] result=new result[10];
and initialize it with -1.
sending each value from index[]in the order and make sure that each one is satifying the given condtions.
that
i=index;
while(i>=0)
{
if(i-1>=0 && arr[i]>arr[i-1])
break;
if(i-1>=0 && arr[i]<arr[i-1])
result[i-1]=result[i]+1;
else
if(i-1>=0 && arr[i]==arr[i-1])
result[i-1]=1
i--;
}
//similary towards the right
i=index;
while(i<arr.length)
{
if(i+1<arr.length && arr[i]>arr[i+1])
break;
if(i+1<arr.length && arr[i]<arr[i+1])
result[i+1]=1+result[i];
else
if(i+1<arr.length && arr[i]==arr[i+1])
result[i+1]=1
i++;
}
so result array will be like this for index 1
2 1 2 3 - - - - - -
then for index 7
2 1 2 5(its modifed from 3) 4 3 2 1 1
followe by indeices :8 9 2 6 5 4 3 0
which all satifies the condtion and more modification occurs in this case..so total number of candies =22
これらの可能な評価構成を考えてみてください: 1 2 3 4 5 または任意の増加シーケンスと 5 4 3 2 1 または任意の減少シーケンス
最初のケースで何ができますか？1 2 3 4 5 は、キャンディーが 5 4 3 2 1 の場合に割り当てられるキャンディーです。
解決策は、配列を左から右にスキャンし、増加の間隔を特定し、右から左にスキャンし、再び増加の間隔を特定し、このプロセスで最小量のキャンディーを割り当てることによって取得できます。正確な詳細については、コードをご覧ください。
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 100000
int c[N];
int val[N];
int solve(int n)
{
int res=n;
int i=0,value=0;
while(i<n)
{
value=0;
i+=1;
while(i<n && c[i]>c[i-1])
{
value+=1;
val[i]=value;
i+=1;
}
}
i=n-1;
while(i>=0)
{
value=0;
i-=1;
while(i>=0 && c[i]>c[i+1])
{
value+=1;
val[i]=max(val[i],value);
i-=1;
}
}
for(i=0;i<n;++i) res+=val[i];
return res;
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;++i) scanf("%d",&c[i]);
printf("%d\n",solve(n));
return 0;
}
1.Ratings[]与えられたレーティングで初期化します。
2.まずCandy、子供たち全員に1つずつ配ります。したがって、すべてのメンバーVal[]を 1 で初期化します。
3.次に、2 つの隣接する子 (i + 1およびi - 1) をトラバースして、条件が保持されているかどうかを確認します。
4. 条件が決して壊れないトラバーサル全体が得られるまで、これを続けます。これで完了です。
bool done = false;
while (!done)
{
done = true;
for (int i = 0 to i = Ratings.size() - 1)
{
for (int k = 1 and k = -1)
{
int adjacent = i + k;
if (adjacent >= 0 && adjacent < N)
{
if (Ratings[adjacent] > Ratings[i] && Val[adjacent] <= Val[i])
{
Val[adjacent] = Val[i] + 1;
done = false;
}
}
}
}
}