ACM简单题求助
http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1001&cid=5547&hide=0
http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1002&cid=5547&hide=0
http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1003&cid=5547&hide=0
http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1004&cid=5547&hide=0
http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1005&cid=5547&hide=0
http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1006&cid=5547&hide=0
一共六道题，请写下代码还有大体思路！谢谢了哦！每道题10分！
[解决办法]
第五题： 就是个调度问题。
开始时间t1 结束时间t2
0 0 ->存入time[0]
1 2.5 ->存入time[1]
3 6 ->存入time[2]
5 11 ->存入time[3]
7 13 ->存入time[4]
设置初始t1=t2=0
第一个任务开始1，1>time[0],time[1]=1+1.5=2.5
第二个任务开始3, 3>time[1],time[2]=3+3=6
第三个任务开始5, 5<time[2],time[3]=time[2]+5=11
第四个任务开始7.5,7.5<time[3], time[4]=time[3]+2=13
[解决办法]
1003 visual C
#include <stdio.h>#include <string.h>int SafeStrcpy(char *dst, const char *src, int size, char *key){ int len = strlen(src); char *location = strstr(src, key); if (location != NULL) len = location - src; strncpy(dst, src, len); /* 这句可不要 */ return len;}void test(void){ enum {BUFFER_SIZE = 256, KEY_SIZE = 16}; char input[BUFFER_SIZE] = ""; char output[BUFFER_SIZE] = ""; char key[KEY_SIZE] = ""; int len = 0; /* 用于记录所拷贝字符串的长度 */ while (scanf("%s%*c", input) != EOF) { while (1) { scanf("%s%*c", key); if (strcmp(key, "END") == 0) break; if (strcmp(key, "NULL") == 0) key[0] = 0; len = SafeStrcpy(output, input, BUFFER_SIZE, key); if (len == 0) printf("0 NULL\n"); else printf("%d %.*s\n", len, len, output); } }}int main(){ test(); return 0;}
[解决办法]
第一题：哈夫曼树，用一个最小堆，每次选两个最小的长度求和，将和加到最终结果中，并再插入到堆中。
这个过程执行N-1次以后，堆中只剩一个元素，最终结果即为所求：
代码：
#include <stdio.h>#include <queue>#include <vector>using namespace std;priority_queue <int,vector <int>, greater<int> > heap;int main(){ int i, k, n, ans = 0; scanf("%d", &n); for (i=0; i<n; ++i){ scanf("%d", &k); heap.push(k); } for (i=1; i<n; ++i){ k = heap.top(); heap.pop(); k += heap.top(); heap.pop(); ans += k; heap.push(k); } printf("%d\n", ans);}
[解决办法]
第二题：
将关系反过来记录，即将 A作业 需要 B作业先完成，记录成 B作业 是 A作业的前提作业。
再建一个队列。初始状态下将所有入度为0（即没有前置作业）的作业加入队列。
然后从队列中开始处理。
每处理一个作业，将他所能影响的作业的入度 - 1，若减1之后入度为0，则将该节点也加入队列。
始终记录一个最大值，输出即可：
C++代码：
00376165 2010-04-09 18:56:46 Accepted 1002 125 MS 2120 KB GNU C++
#include <stdio.h>#include <string.h>#include <vector>using namespace std;#define MAXN 10010#define MAXM 104int a[MAXN], ans[MAXN], list[MAXN] , degree[MAXN];vector <int> next[MAXN]; // 记录关系，next[i][j] 表示 j作业需要先完成i作业int n, m;int main(){ int cases; int i, j, k, max; scanf("%d", &cases); while (cases--) { scanf("%d", &n); memset(ans, -1, sizeof ans); m = 0; for (i=1; i<=n; ++i) next[i].clear(); for (i=1; i<=n; ++i){ scanf("%d %d", a+i, degree+i); if (degree[i] == 0){ // 入度为0的节点加入初始队列。 list[m++] = i; ans[i] = 0; } for (j=0; j<degree[i]; ++j){ scanf("%d", &k); next[k].push_back(i); // 节点K影响节点I } } max = 0; for (i=0; i<m; ++i){ // 开始处理队列 k = list[i]; ans[k] += a[k]; if (ans[k] > max) // 更新最大值 max = ans[k]; for (j=next[k].size()-1; j>=0; --j){ // 枚举该节点所能影响到的所有节点 if (ans[k] > ans[next[k][j]]) // 更新该作业可开始的最早时间 ans[next[k][j]] = ans[k]; if (--degree[next[k][j]] == 0){ // 若该节点入度为0，则加入队列。 list[m++] = next[k][j]; } } } if (m != n) // 若队列中不足N个作业，说明作业没处理完 puts("No Solution."); else printf("%d\n", max); }}
[解决办法]
第三题，纯水题，用strstr就能搞定：
00376212 2010-04-09 19:18:27 Accepted 1003 0 MS 212 KB GNU C++
#include <stdio.h>#include <string.h>char str[300], key[20];int main(){ char ch, *p; while (scanf("%s", str)!=EOF) { for (scanf("%s", key); strcmp(key, "END"); scanf("%s", key)){ if (strcmp(key, "NULL") == 0){ puts("0 NULL"); continue; } if ( (p = strstr(str, key)) ){ ch = *p; *p = '\0'; printf("%d %s\n", strlen(str), str[0]?str:"NULL"); *p = ch; } else { printf("%d %s\n", strlen(str), str); } } }}
[解决办法]
第四题：
简单题，模拟一下栈的操作就行了。
若栈顶元素等于当前元素，则弹出。
否则若下一个入栈元素小于当前元素，则说明出错，跳出循环。
否则继续压栈直到压入元素等于当前元素为止。
00376229 2010-04-09 19:30:35 Accepted 1004 31 MS 284 KB GNU C++
#include <stdio.h>#include <string.h>#define MAXN 10010int a[MAXN], stack[MAXN];int n, top;int main(){ int i, next, k; for (scanf("%d", &n); n; scanf("%d", &n)){ for (i=1; i<=n; ++i) scanf("%d", a+i); top = 0; next = 1; for (i=1; i<=n; ++i){ if (top && stack[top] == a[i]) top--; else if (a[i] < next) break; else { while (next < a[i]) stack[++top] = next++; ++next; } } puts(i<=n ? "No":"Yes"); }}