poj3061 (méthode de prise de pied)-javaDidacticiel-php.cn

Sous-séquence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 14927		Accepted: 6312

Délai : 1 000 MS

Limite de mémoire : 65 536 Ko

Total des soumissions : 14927

Accepté : 6312

Description

Une séquence de N entiers positifs (10 < N < 100 000), chacun d'eux inférieur ou égal à 10 000, et un entier positif S (S < 100 000 000) sont donnés . Écrivez un programme pour trouver la longueur minimale de la sous-séquence d'éléments consécutifs de la séquence dont la somme est supérieure ou égale à S.

Entrée

<span style="font-size: 18px"><strong>2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5</strong></span>

Copier après la connexion

La première ligne est le nombre de cas de test. Pour chaque cas de test, le programme doit lire les nombres N et S, séparés par un intervalle, à partir de la première ligne. Les numéros de séquence sont donnés dans la deuxième ligne du scénario de test, séparés par des intervalles. La saisie se terminera par la fin du fichier.

<span style="font-size: 18px"><strong>2
3</strong></span>

Copier après la connexion

Sortie

Pour chaque cas, le programme doit imprimer le résultat sur une ligne séparée du fichier de sortie. Si pas de réponse, imprimez 0.

Exemple d'entrée

Exemple de sortie

Source

Europe du Sud-Est 2006

<span style="color: #0000ff">import</span><span style="color: #000000"> java.util.Scanner;

</span><span style="color: #0000ff">public</span> <span style="color: #0000ff">class</span><span style="color: #000000"> Main{

    </span><span style="color: #008000">/**</span><span style="color: #008000">
     * </span><span style="color: #808080">@param</span><span style="color: #008000"> args
     </span><span style="color: #008000">*/</span>
    <span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span><span style="color: #000000"> n,s;
    </span><span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span> map[]=<span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[100000+3<span style="color: #000000">];
    </span><span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span> sum[]=<span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[100000+3<span style="color: #000000">];
    </span><span style="color: #0000ff">public</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> main(String[] args) {
        </span><span style="color: #008000">//</span><span style="color: #008000"> TODO Auto-generated method stub</span>
        Scanner scan=<span style="color: #0000ff">new</span><span style="color: #000000"> Scanner(System.in);
        </span><span style="color: #0000ff">int</span> t=<span style="color: #000000">scan.nextInt();
        </span><span style="color: #0000ff">while</span>(t>0<span style="color: #000000">){
            n</span>=<span style="color: #000000">scan.nextInt();
            s</span>=<span style="color: #000000">scan.nextInt();
            </span><span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i=0;i<n;i++<span style="color: #000000">){
                map[i]</span>=<span style="color: #000000">scan.nextInt();
            }
            sovle();
            t</span>--<span style="color: #000000">;
        }
        
    }
    </span><span style="color: #0000ff">private</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> sovle() {
        </span><span style="color: #008000">//</span><span style="color: #008000"> TODO Auto-generated method stub</span>
        <span style="color: #0000ff">int</span> res=n+1<span style="color: #000000">;
        </span><span style="color: #0000ff">int</span> ss=0,t=0,sum=0<span style="color: #000000">;
        </span><span style="color: #0000ff">for</span><span style="color: #000000">(;;){
            </span><span style="color: #0000ff">while</span>(t<n&&sum<<span style="color: #000000">s){
                sum</span>+=map[t++<span style="color: #000000">];
            }
            </span><span style="color: #0000ff">if</span>(sum<<span style="color: #000000">s){
                </span><span style="color: #0000ff">break</span><span style="color: #000000">;
            }
            res</span>=Math.min(res, t-<span style="color: #000000">ss);
            sum</span>-=map[ss++<span style="color: #000000">];
        }
        </span><span style="color: #0000ff">if</span>(res><span style="color: #000000">n){
            res</span>=0<span style="color: #000000">;
        }
        System.out.println(res);
    }

}</span>

Copier après la connexion

算法设计：代码

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées：

poj3061 取法

source：php.cn

Article précédent：Présentation du calendrier Article suivant：Premiers pas avec les bases de JSP

Déclaration de ce site Web

Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Derniers articles par auteur